Universal Cup Judging System

Universal Cup

実行時間制限: 1 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

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

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.