25340번 - 시간딱딱충

준서는 약속이 있어 $T$초까지 선린랜드로 가야 한다. 현재 시각은 $0$초이고, 준서는 준비를 마친 상태로 집에서 언제 출발할지 고민하고 있다.

준서의 집과 선린랜드 사이에는 $N$개의 신호등이 있다. 선린랜드에 가기 위해서는 $N$개의 신호등을 차례로 건너야 한다.

준서는 약속 시간을 지키기 위해 신호등이 언제 켜지는지 조사했다. $i$번째 신호등의 주기는 $A_i$초이고, 각 주기의 첫 $B_i$초동안 켜져 있다. 신호등의 전원은 $C_i$초에 켜져 그때부터 작동을 시작한다. 횡단보도를 건너는 데에는 $D_i$초가 걸린다.

다시 말해, 어떤 음이 아닌 정수 $X$에 대해, 다음 두 조건을 만족하면 $t$초에 $i$번째 횡단보도를 건널 수 있다.

• $C_i + A_i \times X \leq t$
• $t + D_i \leq C_i + A_i\times X + B_i$

$i$번째 횡단보도 끝 지점에서 $i+1$번째 횡단보도 시작 지점까지 이동하는 데에는 $E_i$초가 걸린다. 편의상 $E_0$는 준서의 집에서 $1$번째 횡단보도 시작 지점까지 이동하는 데 걸리는 시간, $E_N$은 $N$번째 횡단보도 끝 지점에서 선린랜드까지 이동하는 데 걸리는 시간으로 정의한다.

준서는 낭비를 싫어하기 때문에 선린랜드에 도착하는 시간을 딱 $T$초로 맞추고 싶다. 이동 중에 쉬는 시간을 가지는 것 또한 낭비라고 생각하기 때문에, 집에서 출발하고 나서는 최대한 빨리 목적지에 도착해야 한다.

준서에게 출발 시각만 조절하여 약속 장소에 딱 $T$초에 도착할 수 있을지 알려주자.

첫째 줄에 테스트케이스의 개수 $TC$가 주어진다. ($1 \leq TC \leq 300\,000$)

각 테스트케이스는 $N+2$개의 줄로 구성되어 있다.

테스트케이스의 첫째 줄에 정수 $N, T$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 300\,000$, $1 \leq T \leq 10^9$)

테스트케이스의 둘째 줄부터 $N+1$번째 줄까지 $N$개의 줄에 걸쳐, $i$번째 줄에 정수 $A_i, B_i, C_i, D_i$가 공백으로 구분되어 주어진다. ($1 \leq A_i, B_i, D_i \leq 1\,000$, $0 \leq C_i \leq 1\,000$, $D_i \leq B_i < A_i$)

테스트케이스의 $N+2$번째 줄에 $N+1$개의 정수 $E_0, E_1, \cdots, E_N$이 공백으로 구분되어 주어진다. ($1 \leq E_i \leq 1\,000$)

모든 테스트케이스에서 $N$의 합은 $300\,000$을 넘지 않는다.

각 테스트케이스마다 출발 시각만 조절하여 약속 장소에 딱 $T$초에 도착할 수 있다면 "YES", 아니면 "NO"를 출력한다.

• Python 사용자는 PyPy로 제출하는 것을 권장한다.