Universal Cup Judging System

Universal Cup

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Tu e i tuoi due compagni di squadra state partecipando a una gara di programmazione, ma a causa degli esami finali dovete tutti andarvene in anticipo. Ciascuno di voi ha uno specifico orario di partenza $\ell_i$ (il tempo in minuti dopo l'inizio della gara in cui deve andarsene). Dopo la gara, rivedete le soluzioni e vi rendete conto che ogni problema è perfettamente adatto a uno di voi: il problema $i$ viene risolto al meglio dalla persona $p_i$, che può completarlo in $c_i$ minuti senza alcun invio errato. Sfortunatamente, a causa della pressione degli esami, non siete andati bene nella gara originale.

In sogno, vedi la squadra campione dalla diretta streaming: hanno risolto tutti gli $n$ problemi con un tempo di penalità totale $t$. Quando ti svegli, scopri di essere rinato la mattina del giorno della gara. Ora, con un ricordo perfetto di tutti i dettagli dei problemi e della prestazione dei campioni, vuoi determinare se c'è un modo per batterli questa volta.

Le regole della gara stabiliscono che:

  • È disponibile un solo computer, quindi i problemi devono essere risolti in sequenza (uno dopo l'altro).
  • Ogni problema $i$ deve essere assegnato alla persona $p_i$, che deve iniziare a risolverlo prima del proprio orario di partenza $\ell_{p_i}$.
  • Se la persona $p_i$ inizia a risolvere il problema $i$ al tempo $s$, deve finire entro $s + c_i \le \ell_{p_i}$.
  • Il tempo di penalità totale è la somma dei tempi di completamento di tutti i problemi risolti.

Dati $n$, $t$, e i parametri $p_i$ e $c_i$ per ciascun problema, determina se esiste un ordine di risoluzione dei problemi tale che:

  • Tutti gli $n$ problemi vengano risolti.
  • Il tempo di penalità totale sia strettamente minore di $t$.

Se esiste una tale disposizione, stampa YES; altrimenti, stampa NO.

Input

La prima riga contiene un singolo intero $q$ ($1 \le q \le 10^5$), il numero di casi di test. Per ciascun caso di test:

La prima riga contiene quattro interi: $n$, $\ell_1$, $\ell_2$ e $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), che rappresentano il numero di problemi e gli orari di partenza (in minuti dopo l'inizio della gara) dei tre compagni di squadra.

Ciascuna delle successive $n$ righe contiene due interi, $p_i$ e $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), dove $p_i$ indica il compagno di squadra designato per il problema $i$, e $c_i$ è il tempo richiesto (in minuti) perché lo completi.

L'ultima riga contiene un singolo intero $t$ ($1 \le t \le 10^{13}$), che rappresenta il tempo di penalità totale della squadra campione.

La somma di $n$ su tutti i casi di test non supera $10^5$.

Output

Per ciascun caso di test, se esiste un ordine di risoluzione dei problemi che soddisfa i vincoli (tutti i problemi risolti, penalità strettamente minore di $t$), stampa YES; altrimenti, stampa NO.

Esempi

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.