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