#414 Setting Three Contests

Statement

Statement language

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 , and define the completion time of problem for each () as follows.

If $r=1$ or $c_{p_{r-1}}=c_{p_r}$ , then .

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

Input

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

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

Output

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

Constraints

$1 \leq T \leq 100$ .
$1 \leq N \leq 3\,000$ .
The sum of $N$ over all test cases does not exceed .

Subtasks

#	Score	Constraints
1	12	$N\leq 10$ .
2	18	$K=0$ .
3	18	At most two contests contain a problem.
4	20	$N\leq 120$ .

Samples

Input

Output

YES
NO
YES

In the first test case, the problems can be prepared in the order $1,2,3,4$ . Their completion times are $2,5,9,12$ .

In the second test case, regardless of which problem is prepared first, switching is required before preparing the other problem, so both deadlines cannot be met.

In the third test case, every problem belongs to the same contest, so no switching time is incurred.