Državno natjecanje 2012. godine za 1. i 2. razred Srednje Škole - 2. zadatak

Državno natjecanje 2012. godine za 3. i 4. razred Srednje Škole - 2. zadatak

Kriza je svuda oko nas. Zbog toga treba biti vrlo oprezan prilikom odlaska u trgovinu. Ivica je odlučio da prilikom svakog odlaska u kupovinu neće kupiti više od 3 različite stvari.

Međutim, i trgovci su se dosjetili, pa stvari pakiraju u pakete. U paketu se može nalaziti više stvari, a ukoliko se Ivici isplati više kupiti paket (u kojem može biti više potrebnih i nepotrebnih stvari), on će ga kupiti. U trgovini ima neograničena količina svakog paketa, a Ivica je odlučio pomno proučiti cjenike prije odlaska u trgovinu, i u samu kupnju ponijeti minimalnu količinu novca (da ne bi pao u napast i nešto nepotrebno kupio).

ULAZNI PODACI

U prvom retku nalazi se broj S (1 ≤ S ≤ 3), broj različitih stvari koje Ivica treba kupiti. U svakom od sljedećih S redova, nalazi se naziv (jedna riječ koja se sastoji od najviše 20 malih slova engleske abecede) i prirodan broj C (1 ≤ C ≤ 100), koji označava koliko toga artikla Ivica treba kupiti.

U sljedećem retku nalazi se broj T (1 ≤ T ≤ 100) koji označava broj paketa na cjeniku. Svaki od sljedećih T redova opisuje jedan paket. Prvi broj u svakom od tih redova, nazovimo ga k (1 ≤ k ≤ 10), označava koliko različitih artikala ima u paketu. Nakon toga slijedi naziv artikla i njegova količina (odvojeno razmakom, količina je uključivo između 1 i 100). Redak završava cijenom jednog takvog paketa (cijena je između 1 i 1000).

IZLAZNI PODACI

U prvi i jedini redak treba ispisati koliko Ivica najmanje mora ponijeti novca, da bi kupio barem onoliku količinu pojedinog artikla koliko je zamislio. Ukoliko u trgovini nema artikla koji mu treba, treba ispisati 0.

PRIMJERI TEST PODATAKA

ulaz

1
lopata 2
1
2 lopata 1 rukavice 1 10

izlaz

20

ulaz

1
lopata 2
1
1 cipele 1 5

izlaz

0

ulaz

2
lopata 2
jakna 1
3
1 lopata 1 10
1 jakna 1 100
3 jakna 1 lopata 3 rukavice 1 110

izlaz

110

Napomena

U barem 20% test primjera će Ivica kupovati samo jednu vrstu artikla i u 20% test primjera će paketi sadržavati samo jednu vrstu artikla.