Сіз және сіздің екі командаласыңыз бағдарламалау сайысына қатысып жатырсыздар, бірақ қорытынды емтихандарға байланысты барлығыңыз ерте кетуге мәжбүрсіздер. Әрқайсыңыздың нақты кету уақытыңыз $\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