Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Þú 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

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.