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.