Tú y tus dos compañeros de equipo están participando en un concurso de programación, pero debido a los exámenes finales, todos tienen que irse temprano. Cada uno de ustedes tiene un tiempo de salida específico $\ell_i$ (el tiempo en minutos después de que comienza el concurso en el que debes irte). Después del concurso, revisan las soluciones y se dan cuenta de que cada problema se adapta perfectamente a uno de ustedes: el problema $i$ lo resuelve mejor la persona $p_i$, quien puede completarlo en $c_i$ minutos sin ningún envío incorrecto. Desafortunadamente, debido a la presión de los exámenes, no tuvieron un buen desempeño en el concurso original.
En un sueño, ves al equipo campeón en la transmisión en vivo: resolvieron todos los $n$ problemas con un tiempo de penalización total $t$. Cuando despiertas, descubres que has renacido en la mañana del día del concurso. Ahora, con un recuerdo perfecto de todos los detalles de los problemas y del desempeño del campeón, quieres determinar si hay alguna manera de vencerlos esta vez.
Las reglas del concurso establecen:
- Solo hay una computadora disponible, por lo que los problemas deben resolverse secuencialmente (uno tras otro).
- Cada problema $i$ debe asignarse a la persona $p_i$, quien debe comenzar a resolverlo antes de su tiempo de salida $\ell_{p_i}$.
- Si la persona $p_i$ comienza a resolver el problema $i$ en el tiempo $s$, debe terminar cumpliendo $s + c_i \le \ell_{p_i}$.
- El tiempo de penalización total es la suma de los tiempos de finalización de todos los problemas resueltos.
Dados $n$, $t$, y los parámetros $p_i$ y $c_i$ para cada problema, determina si existe un orden para resolver los problemas tal que:
- Se resuelvan todos los $n$ problemas.
- El tiempo de penalización total sea estrictamente menor que $t$.
Si existe tal disposición, imprime YES; de lo contrario, imprime NO.
Entrada
La primera línea contiene un solo entero $q$ ($1 \le q \le 10^5$), el número de casos de prueba. Para cada caso de prueba:
La primera línea contiene cuatro enteros: $n$, $\ell_1$, $\ell_2$ y $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), que representan el número de problemas y los tiempos de salida (en minutos después del inicio del concurso) de los tres compañeros de equipo.
Cada una de las siguientes $n$ líneas contiene dos enteros, $p_i$ y $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), donde $p_i$ denota el compañero designado para el problema $i$, y $c_i$ es el tiempo requerido (en minutos) para que lo complete.
La última línea contiene un solo entero $t$ ($1 \le t \le 10^{13}$), que representa el tiempo de penalización total del equipo campeón.
La suma de $n$ en todos los casos de prueba no supera $10^5$.
Salida
Para cada caso de prueba, si existe un orden de resolución de problemas que satisfaga las restricciones (todos los problemas resueltos y penalización estrictamente menor que $t$), imprime YES; de lo contrario, imprime NO.
Ejemplos
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