Du og de to lagkameratene dine deltar i en programmeringskonkurranse, men på grunn av avsluttende eksamener må dere alle dra tidlig. Hver av dere har et bestemt avreisetidspunkt $\ell_i$ (tiden i minutter etter konkurransestart da du må dra). Etter konkurransen går dere gjennom løsningene og innser at hvert problem passer perfekt for én av dere: problem $i$ løses best av person $p_i$, som kan fullføre det på $c_i$ minutter uten noen feilinnleveringer. Dessverre presterte dere ikke bra i den opprinnelige konkurransen på grunn av eksamenspresset.
I en drøm ser du vinnerlaget fra direktesendingen: de løste alle de $n$ problemene med en total straffetid $t$. Når du våkner, oppdager du at du har blitt gjenfødt om morgenen på konkurransedagen. Nå, med perfekt hukommelse om alle problemdetaljene og vinnernes prestasjon, ønsker du å finne ut om det finnes en måte å slå dem på denne gangen.
Konkurransereglene sier:
- Bare én datamaskin er tilgjengelig, så problemene må løses sekvensielt (ett etter ett).
- Hvert problem $i$ må tildeles person $p_i$, som må begynne å løse det før avreisetidspunktet sitt $\ell_{p_i}$.
- Hvis person $p_i$ begynner å løse problem $i$ ved tidspunkt $s$, må vedkommende være ferdig innen $s + c_i \le \ell_{p_i}$.
- Den totale straffetiden er summen av fullføringstidene for alle løste problemer.
Gitt $n$, $t$, og parametrene $p_i$ og $c_i$ for hvert problem, avgjør om det finnes en rekkefølge å løse problemene i slik at:
- Alle $n$ problemer blir løst.
- Den totale straffetiden er strengt mindre enn $t$.
Hvis et slikt oppsett finnes, skriv ut YES; ellers, skriv ut NO.
Inndata
Den første linjen inneholder et enkelt heltall $q$ ($1 \le q \le 10^5$), antallet testtilfeller. For hvert testtilfelle:
Den første linjen inneholder fire heltall: $n$, $\ell_1$, $\ell_2$ og $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), som representerer antallet problemer og avreisetidspunktene (i minutter etter konkurransestart) for de tre lagkameratene.
Hver av de påfølgende $n$ linjene inneholder to heltall, $p_i$ og $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), der $p_i$ angir den utpekte lagkameraten for problem $i$, og $c_i$ er tiden (i minutter) vedkommende trenger for å fullføre det.
Den siste linjen inneholder et enkelt heltall $t$ ($1 \le t \le 10^{13}$), som representerer den totale straffetiden til vinnerlaget.
Summen av $n$ over alle testtilfeller overstiger ikke $10^5$.
Utdata
For hvert testtilfelle, hvis det finnes en rekkefølge å løse problemene i som tilfredsstiller kravene (alle problemer løst, straffetid strengt mindre enn $t$), skriv ut YES; ellers, skriv ut NO.
Eksempler
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