7. Nádlab

Kristíne sa podarilo byť úspešným riešiteľom jej obľúbeného Trojsten korešpondenčného semináru, čím si zaslúžila účasť na jeho letnom sústredení. V rámci štandardného týrania detí na Lesnej Omege je potrava iba na prídel za dobré správanie. Účastníci za dobré skutky ako pomáhanie pri budíčkoch, zúčastňovanie sa rozcvičiek, aktivitu na prednáškach, čistenie záchodov a iné získavajú jednorázové stravné lístky.

Niekoľko svedkov pozorovalo Kristínu nekalo sa škeriť.

Úloha

Lístok môže vyzerať napríklad takto:

+-------+
| 0247g |
|   11% |
+-------+

Všetky lístky vyzerajú rovnako, líšia sa iba v číselných hodnotách. Môžeme vidieť, že na každom lístku sú dve čísla, jedno končiace sa g a druhé ukončené \%. Lístok sa dá teda využiť buď tak, že účastník dostane určité množstvo gramov, alebo určité percento zostávajúceho jedla v hrnci.

Kristína vie, že dnešná večera je granadír. Celé sústredenie si odkladala stravné lístky a podarilo sa jej ich nahrabať až \(N\). Cieľ je jasný a nenechá sa ničím a nikým zastaviť - získať všetok granadír pre seba.

Ale dá sa to vôbec? Lístky vie použiť v ľubovoľnom poradí a pre každý si vie samozrejme vybrať, akým z daných dvoch spôsobov ho chce uplatniť. Pomôžte jej zistiť, ako má lístky použiť aby nahonobila najmasívnejšie množstvo granadíru. Krisína pevne verí, že kuchyňa je čestná a prípadné dlhy jej budú vyplatené na ďalšom sústredení. Jej cieľom je teda maximalizovať zisk granadíru a výsledný zostatok kuchyne môže byť záporný.

Formát vstupu

Na prvom riadku je jedno číslo \(V\) (\(1 \leq V \leq 10\)) udávajúce počet večerí. Nasleduje \(V\) popisov večerí, pričom všetky sú navzájom nezávislé. Pre každú večeru je na vstupe nasledovné:

V prvom riadku sú dve čísla \(N_v\) (\(1 \leq N_v \leq 40\)) a \(H_v\) (\(0 \leq H_v \leq 10^9\)) udávajúce počet kartičiek a hmotnosť navareného granadíru.

Nasleduje \(N_v\) riadkov, každý tvaru <A>g <B>% kde <A> (\(0 \leq A \leq 10^4\)) a <B> (\(0 \leq B \leq 100\)) sú už spomínané dve čísla napísané na kartičke.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Na výstup vypíšte \(V\) odpovedí ako postupovať pri jednotlivých večeriach. V každej odpovedi vypíšte \(N_i\) riadkov, každý vo formáte <L> <T>, kde <L> je číslo lístku indexované od jednotky a <T> je spôsob akým tento lístok chceme použiť, teda buď g alebo %. Poradie lístkov na výstupe určuje v akom poradí ich chcete uplatniť.

Riešenie je považované za správne ak sa od optimálneho riešenia líši maximálne o \(10^{-9}\) v absolútnej alebo relatívnej hodnote.

Príklady

Input:

1
3 1000
10g 2%
20g 1%
30g 1%

Output:

1 %
2 g
3 g

Po uplatnení prvého lístku máme 20g a zostáva 980g, po uplatnení zvyšnych dvoch máme 70g a zostáva 930g.

Input:

1
3 1010
9g 1%
20g 1%
99g 10%

Output:

3 %
1 %
2 g

Dokopy získame 130.09g.

Input:

1
3 1010
9g 1%
20g 1%
100g 10%

Output:

1 %
2 g
3 g

Dokopy získame 130.10g.

Input:

1
3 10
10g 1%
10g 1%
10g 1%

Output:

3 g
1 g
2 g

Dokopy “získame” 30g, aj keď je to viac ako je reálne k dispozícii.