I — Házifeladat-írás

Ignatius épp most érkezett vissza az iskolába a 30. ACM ICPC programozó versenyről, és rengeteg házi feladat vár rá. Mindegyik tanár adott neki egy határidőt a házi feladat benyújtására. Ha Ignatius valamely tárgyból a határidő után adja be a házi feladatot, a tanár minden késedelmes nap után le fog vonni 1 pontot a vizsgapontszámából. Ahogy azzal bizonyára tisztában vagy, a házifeladat-írás mindig hosszú időt vesz igénybe. Ignatius ezért arra kér, hogy segíts neki meghatározni a házi feladatai megírásának egy olyan sorrendjét, amely a lehető legkevesebb pontlevonást eredményezi.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. A bemenet első sorában egyetlen T egész szám szerepel, amely a tesztesetek számát adja meg. Ezt T teszteset leírása követi. Minden teszteset egy N pozitív egész számmal, a házi feladatok számával kezdődik (1 ≤ N ≤ 15). A következő N sor mindegyike egy S sztringet, egy D egész számot és egy C egész számot tartalmaz. S a tantárgy legfeljebb 100 karakter hosszúságú nevét, D a tantárgy házi feladatának napokban mért határidejét, C pedig a tantárgy házi feladatának megírásához szükséges napok számát adja meg.

Megjegyzés: A tantárgynevek ábécérendben lesznek megadva, így egyszerűbben megoldható a feladat.

A kimenet specifikációja

Minden tesztesetre először a pontlevonások összegének legkisebb értékét kell a kimenetre írni, majd soronként egy tantárgynevet a megfelelő sorrendben. Ha több megfelelő rendezettség is lenne, akkor az ábécérend szerinti elsőt kell megadni.

Példa bemenet

1. 2
2. 3
3. Computer 3 3
4. English 20 1
5. Math 3 2
6. 3
7. Computer 3 3
8. English 6 3
9. Math 6 3

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 2
2. Computer
3. Math
4. English
5. 3
6. Computer
7. English
8. Math

letöltés szöveges állományként

Segítség

A második tesztesetben mind a Computer→English→Math, mind a Computer→Math→English sorrend összesen 3 pont levonását eredményezi. Mivel az „English” szó előbb jelenik meg a bemeneten, mint a „Math” szó, ezért az első sorrendet választjuk. Ez eredményezi ugyanis az ábécérend szerinti első rendezettséget.