Universal Cup Judging System

Universal Cup

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

당신과 두 명의 팀원은 프로그래밍 대회에 참가하고 있지만, 기말고사 때문에 모두 일찍 떠나야 합니다. 각자 대회가 시작한 후 떠나야 하는 특정 퇴장 시각 $\ell_i$(분 단위)가 정해져 있습니다. 대회가 끝난 후 풀이를 복기하면서, 여러분은 각 문제가 세 사람 중 한 명에게 완벽하게 들어맞는다는 사실을 깨달았습니다. $i$번 문제는 $p_i$번 팀원이 푸는 것이 가장 좋으며, 그는 잘못된 제출 없이 $c_i$분 만에 문제를 해결할 수 있습니다. 안타깝게도 시험에 대한 압박감 때문에 원래 대회에서는 좋은 성적을 거두지 못했습니다.

꿈속에서 당신은 생중계를 통해 우승 팀을 보았습니다. 그들은 $n$개의 문제를 모두 해결했고 총 패널티 시간은 $t$였습니다. 잠에서 깨어났을 때, 당신은 대회 당일 아침으로 회귀했다는 사실을 알게 되었습니다. 이제 모든 문제의 세부 사항과 우승 팀의 기록을 완벽하게 기억하고 있는 당신은, 이번에 그들을 이길 방법이 있는지 알아내고자 합니다.

대회 규칙은 다음과 같습니다:

  • 사용할 수 있는 컴퓨터는 단 한 대뿐이므로, 문제들은 순차적으로(하나씩 차례대로) 풀어야 합니다.
  • 각 문제 $i$는 반드시 $p_i$번 팀원에게 배정되어야 하며, 그는 자신의 퇴장 시각 $\ell_{p_i}$ 이전에 풀이를 시작해야 합니다.
  • 만약 $p_i$번 팀원이 시각 $s$에 문제 $i$를 풀기 시작했다면, 반드시 $s + c_i \le \ell_{p_i}$까지 끝내야 합니다.
  • 총 패널티 시간은 해결한 모든 문제의 완료 시각의 합입니다.

$n$, $t$, 그리고 각 문제의 매개변수 $p_i$와 $c_i$가 주어질 때, 다음 조건을 만족하는 문제 풀이 순서가 존재하는지 판별하세요:

  • $n$개의 문제가 모두 해결됩니다.
  • 총 패널티 시간이 $t$보다 엄격히 작습니다.

그러한 배치 방법이 존재하면 YES를, 그렇지 않으면 NO를 출력합니다.

입력

첫 번째 줄에는 테스트케이스의 개수를 나타내는 정수 $q$($1 \le q \le 10^5$)가 주어집니다. 각 테스트케이스에 대하여:

첫 번째 줄에는 문제의 개수와 세 팀원의 퇴장 시각(대회 시작 후 경과한 분)을 나타내는 네 정수 $n$, $\ell_1$, $\ell_2$, $\ell_3$($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$)가 주어집니다.

다음 $n$개의 줄에는 각각 두 정수 $p_i$와 $c_i$($1 \le p_i \le 3$, $1 \le c_i \le 300$)가 주어지며, 여기서 $p_i$는 문제 $i$를 담당하는 팀원을 나타내고, $c_i$는 그 팀원이 문제를 완료하는 데 걸리는 시간(분)입니다.

마지막 줄에는 우승 팀의 총 패널티 시간을 나타내는 정수 $t$($1 \le t \le 10^{13}$)가 주어집니다.

모든 테스트케이스에 걸친 $n$의 합은 $10^5$을 초과하지 않습니다.

출력

각 테스트케이스마다 제약 조건(모든 문제를 해결하고, 패널티가 $t$보다 엄격히 작음)을 만족하는 문제 풀이 순서가 존재하면 YES를, 그렇지 않으면 NO를 출력합니다.

예제

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.