Bio jednom jedan film. Vi stojite ispred bioskopa i pitali ste ~N~ ljudi da vam ispričaju jednu scenu iz filma. Kako su pukom koincidencijom svi ti ljudi takođe odlični programeri kao i vi, svako od njih vam je ispričao jednu scenu, predstavljenu kao string malih slova engleske abecede, uz napomenu da se ta scena javlja u filmu tačno jednom. Vaš zadatak je da rekonstruišete film, tačnije, da pronađete string ~S~ najkraće moguće dužine koji će svaku scenu sadržati tačno jednom, takav da se taj string sastoji samo od prvih ~K~ malih slova engleske abecede.

Opisi funkcija

Potrebno je da implementirate funkciju

• ~Resi(N, K, L[\ldots], A[\ldots][\ldots], S[\ldots])~

koja treba da nađe string opisan u tekstu zadatka. ~N~ označava broj ljudi koji su vam rekli jednu scenu iz filma. ~K~ je broj koji označava koliko prvih malih slova engleske abecede možete koristiti za konstruisanje filma. ~L~ je niz dužine ~N~ koji sadrži dužine datih scena. ~A~ je niz nizova, gde elementi ~A[i][1], \ldots, A[i][L[i]]~ čine ~i~-tu scenu. Svi ovi elementi su mala slova engleske abecede. Ukoliko takav string postoji, pronađeni string minimalne dužine smestite u niz ~S~ počev od pozicije ~1~, a njegovu dužinu vratite kao rezultat funkcije. Ukoliko takav string ne postoji, dovoljno je da iz funkcije vratite broj ~-1~. Garantuje se da će za string ~S~ biti rezervisano dovoljno memorije da ceo rezultujući string može da stane. Svi nizovi su indeksirani od 1.

Primeri

Primer 1

Neka je ~N=6, K=26~, a stringovi su ave, venge, ger, rs, r, av. Rešenje je string avengers. Vaša funkcija treba da upiše ovaj string na pozicije ~S[1], \ldots, S[8]~ i da vrati broj ~8~.

Primer 2

Neka je ~N=2, K=2~, a stringovi su ababa, aba. Rešenje ne postoji. U ovom slučaju dovoljno je da vaša funkcija vrati broj ~-1~.

Ograničenja

• ~1 \leq N \leq 14~
• ~1 \leq K \leq 26~
• ~L_i \geq 1~
• ~\sum_{i=1}^N L_i \leq 150~

Podzadaci

• Podzadatak 1 [14 poena]: ~K = 2~, ukoliko rešenje postoji, tada je ono ne duže od ~18~.
• Podzadatak 2 [12 poena]: ~N = 2~
• Podzadatak 3 [23 poena]: ~N = 3~
• Podzadatak 4 [51 poen]: Bez dodatnih ograničenja.

Detalji implementacije

Potrebno je da pošaljete tačno jedan fajl film.cpp, koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.

Vaša funkcija mora biti sledećeg oblika:

int Resi(int N, int K, int* L, char** A, char* S);

Vašim programima je dozvoljeno da menjaju sadržaj nizova/matrica, ali ne smeju da pristupaju van granica datih nizova.

Testiranje i eksperimentisanje

Uz zadatak, obezbeđen vam je "template" fajl code.cpp koji možete koristiti i menjati po potrebi. Takođe vam je obezbeđen program grader.cpp koji služi da lakše testirate kodove. Ovaj program učitava sa standardnog ulaza sledeće podatke:

• U prvom redu brojeve ~N, K~,
• U narednih ~N~ redova po jedan string - ~A_i~.

Zatim ovaj program zove vašu funkciju. Neka je vaša funkcija vratila broj ~X~. Ukoliko je ~X < 0~, štampa se samo ~X~. U suprotnom, štampa se ~X~ i prvih ~X~ karaktera niza ~S~. Kodove ovih programa možete menjati po potrebi.