Þú og tveir liðsfélagar þínir takið þátt í forritunarkeppni, en vegna lokaprófa þurfið þið öll að fara snemma. Hvert ykkar hefur ákveðinn brottfarartíma $\ell_i$ (tímann í mínútum eftir að keppnin hefst þegar þú verður að fara). Eftir keppnina farið þið yfir lausnirnar og áttið ykkur á því að hvert dæmi hentar einum ykkar fullkomlega: dæmi $i$ er best leyst af einstaklingi $p_i$, sem getur klárað það á $c_i$ mínútum án nokkurra rangra skilanna. Því miður gekk ykkur ekki vel í upprunalegu keppninni vegna prófálags.
Í draumi sérðu sigurliðið í beinni útsendingu: þeir leystu öll $n$ dæmin með heildarrefsingartíma $t$. Þegar þú vaknar uppgötvar þú að þú hefur endurfæðst að morgni keppnisdagsins. Nú, með fullkomið minni um öll smáatriði dæmanna og frammistöðu meistaranna, viltu komast að því hvort hægt sé að sigra þá í þetta sinn.
Keppnisreglurnar segja:
- Aðeins ein tölva er í boði, þannig að leysa verður dæmin í röð (eitt af öðru).
- Úthluta verður hverju dæmi $i$ til einstaklings $p_i$, sem verður að byrja að leysa það fyrir brottfarartíma sinn $\ell_{p_i}$.
- Ef einstaklingur $p_i$ byrjar að leysa dæmi $i$ á tíma $s$ verður hann að ljúka því fyrir $s + c_i \le \ell_{p_i}$.
- Heildarrefsingartíminn er summa lokatíma fyrir öll leyst dæmi.
Með gefin $n$, $t$, og stika $p_i$ og $c_i$ fyrir hvert dæmi, ákvarðið hvort til sé röð til að leysa dæmin þannig að:
- Öll $n$ dæmin séu leyst.
- Heildarrefsingartíminn sé strangt minni en $t$.
Ef slík niðurröðun er til skal prenta YES; annars skal prenta NO.
Inntak
Fyrsta línan inniheldur eina heiltölu $q$ ($1 \le q \le 10^5$), fjölda prófunartilvika. Fyrir hvert prófunartilvik:
Fyrsta línan inniheldur fjórar heiltölur: $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$), sem tákna fjölda dæma og brottfarartíma (í mínútum eftir upphaf keppni) liðsfélaganna þriggja.
Hver af næstu $n$ línum inniheldur tvær heiltölur, $p_i$ og $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$), þar sem $p_i$ táknar tilnefndan liðsfélaga fyrir dæmi $i$, og $c_i$ er tíminn (í mínútum) sem hann þarf til að klára það.
Síðasta línan inniheldur eina heiltölu $t$ ($1 \le t \le 10^{13}$), sem táknar heildarrefsingartíma sigurliðsins.
Summa $n$ yfir öll prófunartilvik fer ekki yfir $10^5$.
Úttak
Fyrir hvert prófunartilvik, ef til er röð til að leysa dæmin sem uppfyllir skorðurnar (öll dæmi leyst, refsingartími strangt minni en $t$), prentið YES; annars prentið NO.
Dæmi
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