Universal Cup Judging System

Universal Cup

시간 제한: 1 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.