Universal Cup Judging System

Universal Cup

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Сіз және сіздің екі командаласыңыз бағдарламалау сайысына қатысып жатырсыздар, бірақ қорытынды емтихандарға байланысты барлығыңыз ерте кетуге мәжбүрсіздер. Әрқайсыңыздың нақты кету уақытыңыз $\ell_i$ (сайыс басталғаннан кейін сіз кетуге тиіс минутпен берілген уақыт) бар. Сайыстан кейін сіздер шешімдерді талдап, әрбір есеп араларыңыздағы біреуге өте жақсы сәйкес келетінін түсіндіңіздер: $i$-ші есепті $p_i$-ші адам шығарғаны ең тиімді, ол оны ешқандай қате жіберусіз $c_i$ минут ішінде аяқтай алады. Өкінішке орай, емтихан қысымының кесірінен бастапқы сайыста жақсы өнер көрсете алмадыңыздар.

Түсіңізде тікелей эфирден чемпион команданы көресіз: олар барлық $n$ есепті жалпы айып уақыты $t$ болатындай етіп шығарды. Оянған кезде өзіңіздің сайыс болатын күннің таңында қайта туылғаныңызды байқайсыз. Енді барлық есептердің егжей-тегжейі мен чемпиондардың нәтижесі есіңізде толық сақталғандықтан, бұл жолы оларды жеңудің жолы бар-жоғын анықтағыңыз келеді.

Сайыс ережелері мынадай:

  • Тек бір ғана компьютер қолжетімді, сондықтан есептер тізбектей (бірінен соң бірі) шығарылуы тиіс.
  • Әрбір $i$ есебі $p_i$-ші адамға тағайындалуы керек және ол оны өзінің кету уақыты $\ell_{p_i}$-ге дейін шығаруды бастауы тиіс.
  • Егер $p_i$-ші адам $i$ есебін $s$ уақыт мезетінде шығаруды бастаса, ол оны $s + c_i \le \ell_{p_i}$ дейін аяқтауы керек.
  • Жалпы айып уақыты — шығарылған барлық есептердің аяқталу уақыттарының қосындысы.

Берілген $n$, $t$ және әр есептің $p_i$ мен $c_i$ параметрлері бойынша келесі шарттарды қанағаттандыратын есептерді шығару реті бар-жоғын анықтаңыз:

  • Барлық $n$ есеп шығарылады.
  • Жалпы айып уақыты $t$-дан қатаң кіші болады.

Егер осындай рет бар болса, YES деп, әйтпесе NO деп шығарыңыз.

Кіріс деректер

Бірінші жолда тест жиынтықтарының санын білдіретін бір бүтін сан $q$ ($1 \le q \le 10^5$) берілген. Әрбір тест жиынтығы үшін:

Бірінші жолда төрт бүтін сан берілген: $n$, $\ell_1$, $\ell_2$ және $\ell_3$ ($1 \le n \le 10^5$, $1 \le \ell_1, \ell_2, \ell_3 \le 3 \cdot 10^7$), олар есептер санын және үш командаластың кету уақыттарын (сайыс басталғаннан кейінгі минутпен) білдіреді.

Келесі $n$ жолдың әрқайсысында екі бүтін сан $p_i$ және $c_i$ ($1 \le p_i \le 3$, $1 \le c_i \le 300$) берілген, мұндағы $p_i$ — $i$ есебіне тағайындалған командалас, ал $c_i$ — оны аяқтауға қажетті уақыт (минутпен).

Соңғы жолда чемпион команданың жалпы айып уақытын білдіретін бір бүтін сан $t$ ($1 \le t \le 10^{13}$) берілген.

Барлық тест жиынтықтары бойынша $n$ сандарының қосындысы $10^5$-нен аспайды.

Шығыс деректер

Әрбір тест жиынтығы үшін шектеулерді қанағаттандыратын (барлық есептер шығарылған және айып уақыты $t$-дан қатаң кіші) есептерді шығару реті бар болса, YES, әйтпесе NO деп шығарыңыз.

Мысалдар

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.