Laiko ribojimas: 0.5s

Atminties ribojimas: 128MB

Duomenų failas: perversmas.in

Rezultatų failas: perversmas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Perversmas

Linui atsibodo pasaulyje nuolat vykstantys karai ir nesutarimai. Žinodamas, kad vienintelis būdas viską sutvarkyti ir padaryti pasaulį geresne vieta gyventi yra rasti geresnį pasaulio lyderį. Todėl jis sumanė padaryti perversmą ir tapti pasaulio valdovu.

Tam, kad Linui pavyktų užvaldyti pasaulį, jam reikia papirkti N politikų (jų balsai padėtų parlamente gauti didžiąją daugumą). Kiekvienas politikas turi savo papirkimo kainą c_i bei pinigų sumą r_i, kurią jis atiduos iš savo rėmėjų Linui (žinoma, tik tada, kai Linui pavyks nusipirkti politiko balsą).

Jums reikės patikrinti ar Linui pavyks iš turimų pinigų kažkokia tvarka papirkti visus politikus.

Įvestis

Įvesties failą sudarys iki 30 testų.

Kiekvieną testą sudarys N+1 eilutė. Pirmojoje testo eilutėje bus pateikti du skaičiai N ir M, atitinkamai politikų kiekis bei pradinis Lino kapitalas (1\\leqN\\leq10^4,0\\leqM\\leq10^6). Likusiose testo N eilučių bus pateiktas politiko vardas (viename teste politikas su tokiu vardu bus paminėtas tik vieną kartą), sudarytas iš lotyniškų raidžių bei tarpų (vardas sudarytas iš nedaugiau kaip 100 simbolių), kuris bus pabaigtas dvitaškiu bei du tarpu atskirti skaičiai c_i ir r_i (0\\leqc_i,r_i\\leq10^{12}).

Testai pabaigiami eilute '0 0'

Išvestis

Jei Linui pavyks padaryti perversmą, išveskite žodį TAIP, kitu atveju - NE

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 100
Martynas: 75 60
Ignas: 75 60
Arturas: 91 60
Vytis: 40 40
Vytautas: 60 80
3 0
Daumilas: 0 25
Marijonas: 0 25
Vladimir: 30 10
0 0
 
NE
TAIP