Vous et vos deux coéquipiers participez à un concours de programmation, mais en raison des examens finaux, vous devez tous partir plus tôt. Chacun de vous a une heure de départ spécifique $\ell_i$ (le temps en minutes après le début du concours auquel vous devez partir). Après le concours, vous passez en revue les solutions et réalisez que chaque problème convient parfaitement à l'un d'entre vous : le problème $i$ est résolu de manière optimale par la personne $p_i$, qui peut le terminer en $c_i$ minutes sans aucune soumission erronée. Malheureusement, à cause de la pression des examens, vous n'avez pas obtenu un bon résultat lors du concours initial.
Dans un rêve, vous voyez l'équipe championne lors de la diffusion en direct : elle a résolu les $n$ problèmes avec une pénalité de temps totale $t$. À votre réveil, vous découvrez que vous vous êtes réincarné le matin même du jour du concours. Maintenant, avec un souvenir parfait de tous les détails des problèmes et de la performance des champions, vous voulez déterminer s'il existe un moyen de les battre cette fois-ci.
Les règles du concours stipulent :
- Un seul ordinateur est disponible, de sorte que les problèmes doivent être résolus séquentiellement (les uns après les autres).
- Chaque problème $i$ doit être attribué à la personne $p_i$, qui doit commencer à le résoudre avant son heure de départ $\ell_{p_i}$.
- Si la personne $p_i$ commence à résoudre le problème $i$ à l'instant $s$, elle doit terminer au plus tard à $s + c_i \le \ell_{p_i}$.
- La pénalité de temps totale est la somme des temps d'achèvement de tous les problèmes résolus.
Étant donné $n$, $t$, ainsi que les paramètres $p_i$ et $c_i$ pour chaque problème, déterminez s'il existe un ordre de résolution des problèmes tel que :
- Tous les $n$ problèmes soient résolus.
- La pénalité de temps totale soit strictement inférieure à $t$.
Si un tel arrangement existe, affichez YES ; sinon, affichez NO.
Entrée
La première ligne contient un seul entier $q$ ($1 \le q \le 10^5$), le nombre de cas de test. Pour chaque cas de test :
La première ligne contient quatre entiers : $n$, $\ell_1$, $\ell_2$ et $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), représentant le nombre de problèmes et les heures de départ (en minutes après le début du concours) des trois coéquipiers.
Chacune des $n$ lignes suivantes contient deux entiers, $p_i$ et $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), où $p_i$ désigne le coéquipier attitré pour le problème $i$, et $c_i$ est le temps requis (en minutes) pour qu'il le termine.
La dernière ligne contient un seul entier $t$ ($1 \le t \le 10^{13}$), représentant la pénalité de temps totale de l'équipe championne.
La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^5$.
Sortie
Pour chaque cas de test, s'il existe un ordre de résolution des problèmes qui satisfait les contraintes (tous les problèmes résolus, pénalité strictement inférieure à $t$), affichez YES ; sinon, affichez NO.
Exemples
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