35507번 - Good Bye, 설탕 배달!

https://www.acmicpc.net/problem/2839

PS 초보자 동규는 요즘 단계별로 풀어보기를 푸는 것에 맛들려 있다. 오늘의 문제는 바로 설탕 배달이다! 동규는 너무 쉬운 것 아니냐며 뚝딱 코드를 짜서 제출했다.

<Figure 1. 무슨 일이 일어났는지는 여러분이 더 잘 알 것이다.>

동규는 이 설움을 달래기 위해 문제집을 구해 더 많은 문제를 풀기로 결심했다.

$N$개의 문제로 구성된 문제집의 $i$번째 문제는 지금보다 지식이 $a_i$ 더 필요하고, 구현력이 $b_i$만큼 더 필요하고, 사고력이 $c_i$만큼 더 필요하다.

동규는 하루를 사용해 아직 안 푼 문제 중 하나를 풀 수 있다. 그렇지 않다면, 하루를 사용하여 지식을 $1$ 쌓거나, 구현력을 $1$ 올리거나, 사고력을 $1$ 키울 수 있다.

동규는 $i$번째 문제를 늦어도 $p_i$일차까지는 해결하려고 한다. 마감일은 항상 뒤쪽 문제로 갈수록 더 여유로워진다. 즉, $p_{i+1}$은 $p_i$와 같거나 더 크다. ($1\le i\le N-1$)

동규가 계획을 지킬 수 있을까?

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에 정수 $N$이 주어진다.

각 테스트 케이스의 다음 $N$개의 줄에 각 문제의 정보를 나타내는 정수 $a_i,b_i,c_i,p_i$가 공백으로 구분되어 주어진다. $a_i,b_i,c_i$는 각각 $i$번째 문제를 풀기 위해 필요한 지식, 구현력, 사고력을 의미하며, $p_i$는 늦어도 해당 일자까지는 문제를 풀어야 함을 나타낸다.

$T$줄에 걸쳐 각 줄에 계획을 지킬 수 있다면 YES, 그러지 못하면 NO를 출력한다.

• $1\le T\le 300\,000$
• $1\le N\le 300\,000$
• $0\le a_i,b_i,c_i\le 10^{18}$ ($1 \le i \le N$)
• $1\le p_i\le 10^{18}$ ($1 \le i \le N$)
• $p_i \le p_{i+1}$ ($1 \le i \le N-1$)
• 모든 테스트 케이스에서 $N$의 합은 $300\, 000$ 이하이다.

$a_i, b_i, c_i, p_i$가 32비트 정수 범위를 넘을 수 있음에 유의하라.