#414 세 대회 세팅

Statement

다다스는 세 개의 대회에 출제할 문제를 준비하고 있다. 준비해야 하는 문제는 $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}$ 를 만족하도록 문제를 준비할 수 있는지 판단하여라.

Input

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

$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$

Output

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

Constraints

$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$ ).
입력으로 주어지는 모든 값은 정수이다.

Subtasks

#	점수	제한
1	12	$N\leq 10$ .
2	18	$K=0$ .
3	18	문제가 존재하는 대회는 두 개 이하이다.
4	20	$N\leq 120$ .
5	32	추가적인 제약이 없다.

Samples

입력

출력

YES
NO
YES

첫 번째 테스트 케이스에서는 문제를 $1,2,3,4$ 의 순서로 준비할 수 있다. 각 문제의 완료 시각은 차례로 $2,5,9,12$ 이다.

두 번째 테스트 케이스에서는 어느 문제를 먼저 준비하더라도 다른 문제를 준비하기 전에 전환 시간이 필요하므로 두 문제를 모두 기한 안에 끝낼 수 없다.

세 번째 테스트 케이스의 모든 문제는 같은 대회의 문제이므로 전환 시간이 발생하지 않는다.

해설

해설 보기