Sinä ja kaksi joukkuetoveriasi osallistutte ohjelmointikilpailuun, mutta loppukokeiden vuoksi teidän kaikkien on lähdettävä aikaisin. Jokaisella teistä on tietty lähtöaika $\ell_i$ (aika minuutteina kilpailun alkamisen jälkeen, jolloin sinun on lähdettävä). Kilpailun jälkeen käytte läpi malliratkaisut ja huomaatte, että jokainen tehtävä sopii täydellisesti jollekin teistä: tehtävän $i$ ratkaisee parhaiten henkilö $p_i$, joka pystyy saamaan sen valmiiksi $c_i$ minuutissa ilman yhtäkään väärää palautusta. Valitettavasti koepaineiden vuoksi ette menestyneet hyvin alkuperäisessä kilpailussa.
Unessa näet voittajajoukkueen suorasta lähetyksestä: he ratkaisivat kaikki $n$ tehtävää kokonaissakkoajalla $t$. Kun heräät, huomaat syntyneesi uudelleen kilpailupäivän aamuun. Nyt, muistaen täydellisesti kaikkien tehtävien yksityiskohdat ja mestareiden suorituksen, haluat selvittää, onko tällä kertaa olemassa tapaa voittaa heidät.
Kilpailun säännöt määräävät:
- Käytettävissä on vain yksi tietokone, joten tehtävät on ratkaistava peräkkäin (yksi toisensa jälkeen).
- Jokainen tehtävä $i$ on annettava henkilölle $p_i$, jonka on aloitettava sen ratkaiseminen ennen lähtöaikaansa $\ell_{p_i}$.
- Jos henkilö $p_i$ aloittaa tehtävän $i$ ratkaisemisen ajanhetkellä $s$, hänen on saatava se valmiiksi viimeistään silloin, kun $s + c_i \le \ell_{p_i}$.
- Kokonaissakkoaika on kaikkien ratkaistujen tehtävien valmistumisaikojen summa.
Kun annetaan $n$, $t$ sekä parametrit $p_i$ ja $c_i$ jokaiselle tehtävälle, määritä, onko olemassa sellaista tehtävien ratkaisujärjestystä, että:
- Kaikki $n$ tehtävää saadaan ratkaistua.
- Kokonaissakkoaika on aidosti pienempi kuin $t$.
Jos tällainen järjestely on olemassa, tulosta YES; muussa tapauksessa tulosta NO.
Syöte
Ensimmäinen rivi sisältää yhden kokonaisluvun $q$ ($1 \le q \le 10^5$), testitapausten lukumäärän. Jokaisessa testitapauksessa:
Ensimmäinen rivi sisältää neljä kokonaislukua: $n$, $\ell_1$, $\ell_2$ ja $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), jotka kuvaavat tehtävien lukumäärää ja kolmen joukkuetoverin lähtöaikoja (minuutteina kilpailun alusta).
Jokainen seuraavista $n$ rivistä sisältää kaksi kokonaislukua, $p_i$ ja $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), missä $p_i$ tarkoittaa tehtävään $i$ nimettyä joukkuetoveria ja $c_i$ on aika (minuutteina), jonka hän tarvitsee sen suorittamiseen.
Viimeinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 10^{13}$), joka kuvaa voittajajoukkueen kokonaissakkoaikaa.
Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^5$.
Tuloste
Tulosta jokaista testitapausta kohden YES, jos on olemassa rajoitteet täyttävä tehtävien ratkaisujärjestys (kaikki tehtävät ratkaistaan ja sakkoaika on aidosti pienempi kuin $t$); muussa tapauksessa tulosta NO.
Esimerkit
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