Županijska razina 2019 / Osnovna škola (7. razred) - 3. zadatak

Vitez Jura treba se suočiti s ljutim protivnikom. Da bi umanjio svoj strah, Jura će kupiti najkvalitetniju vitešku opremu od seoskog kovača Đure.

Jura može kupiti neke od pet različitih vrsta opreme: štit, mač, oklop, kacigu i koplje. Od svake vrste kovač može ponuditi nula ili više predmeta koji mogu imati različitu snagu i masu. Primjerice, kovač može Juri ponuditi štit, koplje i dva različita mača. Jura će kupiti najviše jedan predmet svake vrste (ne može kupiti oba mača).

Jura svoj strah mjeri u jedinicama straha i procjenjuje da je njegov strah velik S jedinica. Svaki predmet koji Jura kupi smanjit će njegov strah za onoliko jedinica koliko iznosi snaga tog predmeta. Jura želi potpuno nadvladati strah (smanjiti ga na 0 ili negativan broj jedinica), ali uz to želi biti što lakši u borbi, pa želi da ukupna masa kupljenih predmeta bude što manja.

Pomozite Juri i napišite program koji za ponuđene predmete računa najmanju ukupnu masu koju Jura može dobiti nekim odabirom predmeta različitih vrsta čija je ukupna snaga veća ili jednaka njegovom strahu. Test podaci bit će takvi da će Jurin strah biti moguće nadvladati. Osim toga, Juru zanima i koja je vrsta predmeta kojeg mu je Đuro ponudio u najviše primjeraka.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi \(N\) \((2 \leq N \leq 10)\), broj ponuđenih predmeta, i \(S\) \((1 \leq S \leq 100)\), količina Jurinog straha. U svakom od sljedećih \(N\) redaka nalazi se opis ponuđenog predmeta: najprije jedna od riječi „stit“, „mac“, „oklop“, „kaciga“ ili „koplje“ (vrsta predmeta), potom prirodan broj između 1 i 20 – snaga navedenog predmeta, i na kraju prirodan broj između 1 i 20 – masa navedenog predmeta.

Izlazni podaci

U prvi redak ispišite vrstu predmeta kojeg je Đuro ponudio u najviše primjeraka. Ako je takvih predmeta više, ispišite onaj čiji je naziv leksikografski najmanji. Nazivi predmeta poredani leksikografski, od najmanjeg prema najvećem, su „kaciga“, „koplje“, „mac“, „oklop“ i „stit“. U drugi redak ispišite traženu masu iz teksta zadatka.

Bodovanje

Točan ispis prvog retka vrijedi 4 boda, a točan ispis drugog retka 6 bodova za svaki test podatak. U test podacima ukupno vrijednima 50 bodova, kovač će ponuditi najviše jedan predmet svake vrste, a među ponuđenim predmetima neće se pojaviti niti jedan mač, kao niti štit.

Test podaci

Ulaz

2 3
oklop 5 5
kaciga 5 4

Izlaz

kaciga
4

Ulaz

3 5
koplje 2 5
kaciga 3 6
kaciga 3 1

Izlaz

kaciga
6

Ulaz

6 34
oklop 12 14
stit 11 18
stit 7 15
kaciga 13 6
mac 7 3
koplje 14 10

Izlaz

stit
19

Objašnjenje trećeg test primjera

Štit je ponuđen u dva primjerka, što je više od ostalih predmeta. Za nadvladavanje straha, Jura može odabrati kacigu, mač i koplje.