Zadanie

Jedlo

Počet bodov: 60, časový limit: 1000ms

Keď trávite veľa času hraním počítačových hier, ževraj sa to odrazí na vašom zdraví. Samko sa rozhodol to vykompenzovať tým, že sa bude zdravo stravovať.

Každý vie, že vitamínov je \(13\): sú to \(A, B_1, B_2, B_3, B_5, B_6, B_7, B_9, B_{12}, C, D, E, K\). Vo vyváženej strave musí byť z každého vitamínu aspoň trošku. Samko si teraz ide poskladať svoj denný jedálniček. Na výber má z \(n\) produktov, každý má nejakú cenu \(c\) a obsahuje nejaké látky (nie nutne len vitamíny).

Poraďte Samkovi, čo má kúpiť, aby v jeho nákupe boli zastúpené všetky vitamíny a aby ho to vyšlo čo najlacnejšie.

Vstup a výstup

Na prvom riadku vstupu je číslo \(n\): počet produktov. Platí \(1 \leq n \leq 3\,000\).

Na každom z nasledujúcich \(n\) riadkoch je popis jedného produktu v tvare \(m c k l_1 l_2 \ldots l_k\), kde \(m\) je názov produktu, \(c\) je jeho celočíselná cena v centoch, \(k\) je počet látok ktoré obsahuje, a \(l_i\) sú názvy jednotlivých látok. Platí \(1 \leq c \leq 10^8\), \(0 \leq k \leq 20\), všetky názvy pozostávajú z čísel a malých znakov anglickej abecedy a sú dlhé nanajvýš \(10\) znakov. Názvy produktov sú navzájom rôzne. Vitamíny majú názvy a, b1, b2, b3, b5, b6, b7, b9, b12, c, d, e, k.

Ak neexistuje žiadne riešenie, vypíšte \(-1\). V opačnom prípade na prvý riadok výstupu vypíšte medzerami oddelenú celkovú cenu produktov a ich počet. Ďalej vypíšte názvy týchto produktov, každý na samostatný riadok. Ak je viacero optimálnych riešení, môžete vypísať ľubovoľné z nich.

Príklad

Input:

6
koktejl1 1 3 a b1 b2
koktejl2 1 3 b3 b5 b6
koktejl3 1 3 b7 b9 b12
koktejl4 1 3 c d e
koktejl5 97 1 k
superbomba 100 13 a b1 b2 b3 b5 b6 b7 b9 b12 c d e k

Output:

100 1
superbomba

Drahším riešením by bolo kúpiť všetky koktejly, čo by nás vyšlo až \(101\) centov.

Input:

7
koktejl1 1 3 a b1 b2
koktejl2 1 3 b3 b5 b6
koktejl3 1 3 b7 b9 b12
koktejl4 1 3 c d e
koktejl5 97 1 k
bomba1 50 6 a b1 b2 b3 b5 b6
bomba2 50 7 b7 b9 b12 c d e k

Output:

52 3
bomba2
koktejl2
koktejl1

Input:

3
hranolky 100 1 sol
hamburger 100 1 sol
kebab 270 1 nacl

Output:

-1