Setting Three Contests

Dadas is preparing problems for three contests. There are $N$ problems, numbered from $1$ to $N$.

Problem $i$ must be used in contest $c_i$. It takes $e_i$ units of time to prepare, and its preparation must be completed by time $d_i$.

Dadas can prepare only one problem at a time. Let $p_1,p_2,\cdots,p_N$ be the order in which the problems are prepared. Set $t_0=0$, and define the completion time $t_r$ of problem $p_r$ for each $r$ ($1 \leq r \leq N$) as follows.

• If $r=1$ or $c_{p_{r-1}}=c_{p_r}$, then $t_r=t_{r-1}+e_{p_r}$.
• If $r\geq 2$ and $c_{p_{r-1}}\neq c_{p_r}$, then $t_r=t_{r-1}+K+e_{p_r}$.

Thus, preparing problems from different contests consecutively requires an additional $K$ units of switching time. No switching time is required before the first problem.

Determine whether the problems can be ordered so that $t_r\leq d_{p_r}$ holds for every $r$.

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

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

For each test case, print YES if all problems can be prepared by their deadlines, and print NO otherwise.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 3\,000$.
• The sum of $N$ over all test cases does not exceed $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$).
• All values in the input are integers.