Universal Cup Judging System

Universal Cup

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

Вы и двое ваших сокомандников участвуете в соревновании по программированию, но из-за выпускных экзаменов вам всем приходится уйти пораньше. У каждого из вас есть определённое время ухода $\ell_i$ (время в минутах после начала соревнования, когда вы должны уйти). После соревнования вы разбираете решения и понимаете, что каждая задача идеально подходит кому-то одному из вас: задачу $i$ лучше всего решает участник $p_i$, который может сдать её за $c_i$ минут без единой неверной попытки. К сожалению, из-за стресса перед экзаменами в исходном соревновании вы выступили неудачно.

Во сне вы видите прямую трансляцию команды-чемпиона: они решили все $n$ задач с суммарным штрафным временем $t$. Проснувшись, вы обнаруживаете, что переродились утром в день соревнования. Теперь, обладая идеальной памятью о всех деталях задач и результате чемпионов, вы хотите определить, есть ли способ победить их на этот раз.

Правила соревнования гласят:

  • Доступен только один компьютер, поэтому задачи должны решаться последовательно (одна за другой).
  • Каждая задача $i$ должна быть поручена участнику $p_i$, который должен начать решать её до своего времени ухода $\ell_{p_i}$.
  • Если участник $p_i$ начинает решать задачу $i$ в момент времени $s$, он должен закончить её к моменту $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.