Universal Cup Judging System

Universal Cup

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

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

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.