세 대회 세팅

다다스는 세 개의 대회에 출제할 문제를 준비하고 있다. 준비해야 하는 문제는 $N$개이며, 문제에는 $1,2,\cdots,N$의 번호가 붙어 있다.

$i$번 문제는 $c_i$번 대회에 출제해야 한다. 이 문제를 준비하는 데에는 $e_i$의 시간이 필요하며, 시각 $d_i$까지 준비를 끝내야 한다.

다다스는 한 번에 하나의 문제만 준비할 수 있다. 문제를 준비하는 순서를 $p_1,p_2,\cdots,p_N$이라 하자. $t_0=0$으로 두고, 각 $r$ ($1 \leq r \leq N$)에 대해 $p_r$번 문제의 완료 시각 $t_r$을 다음과 같이 정의한다.

• $r=1$이거나 $c_{p_{r-1}}=c_{p_r}$이면, $t_r=t_{r-1}+e_{p_r}$이다.
• $r\geq 2$이고 $c_{p_{r-1}}\neq c_{p_r}$이면, $t_r=t_{r-1}+K+e_{p_r}$이다.

즉, 서로 다른 대회의 문제를 연속해서 준비하면 대회를 전환하는 데 $K$의 시간이 추가로 필요하다. 첫 번째 문제를 준비하기 전에는 전환 시간이 필요하지 않다.

모든 $r$에 대해 $t_r\leq d_{p_r}$를 만족하도록 문제를 준비할 수 있는지 판단하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ K$ $c_1\ e_1\ d_1$ $c_2\ e_2\ d_2$ $\vdots$ $c_N\ e_N\ d_N$

각 테스트 케이스마다 모든 문제를 기한 안에 준비할 수 있다면 YES를, 그렇지 않다면 NO를 한 줄에 출력한다.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 3\,000$.
• 모든 테스트 케이스에 대한 $N$의 합은 $3\,000$ 이하이다.
• $0 \leq K \leq 10^9$.
• $1 \leq c_i \leq 3$ ($1 \leq i \leq N$).
• $1 \leq e_i \leq 10^9$ ($1 \leq i \leq N$).
• $1 \leq d_i \leq 10^{18}$ ($1 \leq i \leq N$).
• 입력으로 주어지는 모든 값은 정수이다.