Universal Cup Judging System

Universal Cup

حد الوقت: 1 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

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

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.