prefix

Anumite structuri biologice pot fi reprezentate prin secvente de constituenti. Constituentii sunt notati cu litere mari. Biologii sunt interesati în descompunerea unei secvente lungi în altele mai scurte, denumite primitive.
Spunem ca o secventa S poate fi compusa dintr-o multime data P de primitive, daca exista n primitive p1, p2, ..., pn în P astfel încât S sa se obtina prin concatenarea lor. Aceeasi primitiva poate aparea în concatenare de mai multe ori sau poate lipsi. De exemplu, secventa ABABACABAAB poate fi obtinuta din multimea de primitive {A, AB, BA, CA, BBC}.
Primele K caractere ale unei secvente S constituie prefixul lui S de lungime K.

Cerinta

Fisierul de intrare prefix.in contine:
- Pe prima linie numarul natural N, care reprezinta numarul de primitive din P (1<=N<=20).
- Urmatoarele 2*N linii contin primitivele. Pentru fiecare primitiva sunt scrise doua linii: pe prima linie este lungimea primitivei, iar pe urmatoarea o succesiune de maxim 20 litere mari, care reprezinta primitiva. Cele N primitive sunt distincte.
- pe urmatoarele linii se afla secventa de examinat, cate un caracter pe o linie. Secventa contine maxim 500000 litere mari, sfârsitul secventei fiind marcat de aparitia caracterului punct.

Date de iesire

In fisierul de iesire prefix.out se va scrie o singura linie pe care se afla lungimea celui mai lung prefix al lui T care poate fi format din elemente ale multimii P.

Exemple

prefix.in	prefix.out
5 1 A 2 AB 3 BBC 2 CA 2 BA A B A B A C A B A A B C .	11