Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Duomenų failas: ekonom_krize.in

Rezultatų failas: ekonom_krize.out

Jei norite pateikti savo sprendimą - prisijunkite.

Ekonominė krizė

Džonas išgirdo apie naują ekonominės krizės bangą. Taigi jis nusprendė nusipirkti daug maisto atsargų gretimoje maisto prekių parduotuvėje, prieš tai kai krizė smogs jam. Džonas nėra labai turtingas, tad jis nusprendė pasinaudoti parduotuvės nuolaidų kortele, kuri leidžia nusipirkti kai kurias prekes pigiau.

Užduotis

Raskite kiek pinigų sutaupyti gali Džonas naudodamasis nuolaidų kortele.

Pradiniai duomenys

Pirmoje eilutėje pateiktas K nusakantis kiek duomenų rinkinių bus. Kiekvieno duomenų rinkinio pirmojoje eilutėje yra du tarpais atskirti skaičiai 1\\leN,M\\le100 kur N yra parduotuvėje esančių prekių skaičius ir M yra Džono pirkinių sąraše esančių prekių skaičius. Tolesnėse N eilučių, kiekvienoje yra nusakoma parduotuvėje esanti prekė, pirmasis prekę apibūdinantis skaičius žymi jos kiekį sandėlyje n_{i}\\le999 toliau yra nurodytos prekės kainos atskirtos tarpu, pirmoji kaina nurodo jos kainą be nuolaidų kortelės, o antroji su 0.00\\lep_{i},c_{i}\\le99.99,c_{i}\\lep_{i}, po tarpo duotas prekės pavadinimas, kuris gali turėti tarpų ir didžiųjų bei mažųjų lotyniškų raidžių. Prekės pavadinimą sudaro nedaugiau nei 100 simbolių, nėra papildomų tarpų prieš ar po pavadinimo. Toliau seka M eilučių, kiekviena apibūdina M_{j} prekę esančią pirkinių sąraše. M_{j} prekė yra apibūdinta skaičiu nurodančiu pageidaujamą prekės kiekį d_{j}\\le999 toliau tarpu atskirtas duotas prekės pavadinimas s_{j}, kuris gali turėti tarpų ir didžiųjų bei mažųjų lotyniškų raidžių. Prekės pavadinimą sudaro nedaugiau nei 100 simbolių, nėra papildomų tarpų prieš ar po pavadinimo. Prekė nurodyta pirkinių sąraše laikoma identiška nurodytai parduotuvės sandėlyje esančiai jeigu jų pavadinimai sutampa, ignoruojant didžiąsias/mažąsias raides.

Rezultatai

Kiekvienam duomenų rinkiniui atskirose eilutėse turi būti išvestas tikslus pinigų kiekis sutaupytas naudojantis nuolaidų kortele.

Pavyzdys

Duomenys Rezultatai 
1
2 3
3 3.00 3.00 Coca Cola
2 6.00 4.50 meat of kangaroo
1 coca cola
3 meat of kangaroo
1 russian vodka
 
3.00