You and your two teammates are participating in a programming contest, but due to the final exams, you all have to leave early. Each of you has a specific departure time $\ell_i$ (the time in minutes after the contest starts when you must leave). After the contest, you review the solutions and realize that each problem is perfectly suited for one of you: problem $i$ is best solved by person $p_i$, who can complete it in $c_i$ minutes without any wrong submissions. Unfortunately, due to the pressure of exams, you didn't perform well in the original contest.
In a dream, you see the champion team from the live broadcast: they solved all $n$ problems with a total penalty time $t$. When you wake up, you discover you've been reborn on the morning of the contest day. Now, with perfect memory of all problem details and the champion's performance, you want to determine if there's a way to beat them this time.
The contest rules state:
- Only one computer is available, so problems must be solved sequentially (one after another).
- Each problem $i$ must be assigned to person $p_i$, who must start solving it before their departure time $\ell_{p_i}$.
- If person $p_i$ starts solving problem $i$ at time $s$, they must finish by $s + c_i \le \ell_{p_i}$.
- The total penalty time is the sum of the completion times for all solved problems.
Given $n$, $t$, and the parameters $p_i$ and $c_i$ for each problem, determine if there exists an order of solving the problems such that:
- All $n$ problems are solved.
- The total penalty time is strictly less than $t$.
If such an arrangement exists, output YES; otherwise, output NO.
Input
The first line contains a single integer $q$ ($1 \le q \le 10^5$), the number of test cases. For each test case:
The first line contains four integers: $n$, $\ell_1$, $\ell_2$, and $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), representing the number of problems and the departure times (in minutes after contest start) of the three teammates.
Each of the following $n$ lines contains two integers, $p_i$ and $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), where $p_i$ denotes the designated teammate for problem $i$, and $c_i$ is the required time (in minutes) for them to complete it.
The last line contains a single integer $t$ ($1 \le t \le 10^{13}$), representing the total penalty time of the champion team.
The sum of $n$ over all test cases does not exceed $10^5$.
Output
For each test case, if there exists an order of solving problems that satisfies the constraints (all problems solved, penalty strictly less than $t$), output YES; otherwise, output NO.
Examples
2
3 100 150 175
1 100
2 25
3 50
401
5 100 200 300
1 30
1 30
1 40
2 110
3 50
1275
YES
NO
1
1 100 300 300
1 300
300
NO