z-party

Mister R slavi rodjendan i pozvao je svoje drustvo. U tom drustvu od
muskaraca se nalaze i Mali Z,
Mister S i Mister A. Ne bi li ucinio celu zabavu jos zanimljivijom, Mister S je
smislio novu igru i predlozio drustvu, koje je drustvo rado prihvatilo.
<br><br>

Igra se igra na sledeci nacin.
Pre pocetka igre, imenu svake devojke sa zabave je komplikovanom
funkcijom dodeljen odredjen broj
koji predstavlja vrednost njenog imena. Funkcija vraca vrednost imena
kao prirodan broj u intervalu [1 .. 5555]. Na zabavi je 9 devojaka, mada
ne zeli svaka devojka da svaki put bude korisceno njeno ime :)
Jedan od cetvorice muskaraca izaziva devojku i igra pocinje.
Prvo se baci kockica. Neka se dobije broj <B>k</B>. Tada devojka <B>(k
mod 4) + 1</B> reci zapise
na papir, tako da zbir duzina svih reci bude najvise 100. Sve
napisane reci, momak
treba u nekom redosledu da postavi u neku veliku rec. Ako se posmatra
ta velika rec, on
treba da tako postavi imena, kao podstringove te velike reci, da zbir vrednosti
imena koje je postavio bude najveci. Kada postavi imena u veliku rec,
dva imena ne smeju
da sadrze slovo na istoj poziciji, odnosno podstringovi koji sadrze
neko ime, moraju biti
disjuktni. Nije obavezno da uvek postoji podstring koji sadrzi svako ime.
Ako momak izabere takav raspored reci u velikoj reci da se u nju mogu
postaviti imena, koristeci data pravila, tako da zbir vrednosti imena
bude najveci, tada devojka koju je izazvao skida jedan deo odece, inace
igra se zavrsava i devojka oblaci svu odecu, ako je ista skinula.
Prvi izaziva Mister S.
Mister S ce vama poslati sve potrebne podatke, a vi mu pomozite da skine devojku
tako sto cete mu svaki put reci maximum koji moze da se dobije nekim rasporedom
imena u velikoj reci koja je dobijena opet nekim najboljim rasporedom reci.
<br><br>

Ulaz:<br>
Sa standardnog ulaza ucitava se broj <B>M</B> (1 <= <B>M</B> <= 4).
Potom sledi M redova. U svakom redu se nalazi jedan string koji
predstavlja rec koju je zapisala devojka.
Zbir duzina <B>M</B> reci je najvise 100. Svaka rec je sastavljena od
malih slova engleskog alfabeta.
Zatim se ucitava broj <B>N</B> (1 <= <B>N</B> <= 9). Potom se u svakom
od narednih N redova
ucitava jedno ime (duzina imena je manja
od 12 i svako ime je sastavljeno od malih slova engleskog alfabeta) i
jedan broj koji predstavlja vrednost tog imena
(vrednost imena ne prelazi 5555).
<br><br>


Izlaz:<br>
Na standardni izlaz ispisati resenje.
<br><br>

Primeri:<br>
Ulaz:<br>
3<br>
nakoma<br>
janatasani<br>
ugabungkatari<br>
4<br>
nina 40<br>
katarina 58<br>
maja 59<br>
natasa 28<br>
<br>
Izlaz:<br>
145<br>
<br>
Mozemo postaviti reci (da bi dobili veliku rec) redosledom 3 , 1 , 2, pa je velika rec
ugabungkatarinakomajanatasani
U toj velikoj reci mozemo naci imena katarina, maja i natasa, a da u isto vreme ta imena sadrze
disjuktne karaktere u velikoj reci.
<br>
Primetimo da smo mogli naci i rec nina sledecom varijacijom 2 , 1 , 3, ali to nam daje manju vrednost :)

<br><br>
Ulaz:<br>
3<br>
akrep<br>
jelzit<br>
dragadragan<br>
3<br>
jelena 16<br>
dragana 17<br>
zita 22<br>
<br>
Izlaz:<br>
22<br>
<br><br>
Ako reci slozimo sledecim redosledom 3 , 2 , 1, dobijamo veliku rec
dragadraganjelzitakrep u kojoj nalazimo ime zita i to nam je resenje.
Mogli smo dobiti i ime dragana redosledom 3 , 1 , 2, ali to nam daje manju vrednost.
Primetimo da ne postoji raspored koji daje ime jelena.