Ви та двоє ваших співкомандників берете участь у змаганні з програмування, але через підсумкові іспити вам усім доводиться піти раніше. У кожного з вас є певний час виходу $\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