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