Algolymp Educational | A world of strings

Cerință

Se dă un număr $N$ și un șir target, $S$, cu $N$ caractere, conținând litere mici ale alfabetului latin.

Aveți la dispoziție $K$ șiruri, conținând litere mici ale alfabetului latin. Știind că puteți folosi orice prefix al acestor șiruri, de oricâte ori este nevoie, care este costul minim pentru a obține șirul inițial prin alipirea (fără suprapunere) prefixelor selectate? Costul se va incrementa cu $1$ pentru fiecare utilizare a unui prefix.

Date de intrare

Pe prima linie se găsește un număr, $N$.
Pe a doua linie se găsește șirul $S$.
Pe a treia linie se găsește un număr, $K$.
Fiecare dintre urmatoarele $K$ linii va conține unul dintre cele $K$ șiruri.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, costul minim pentru a forma șirul inițial. În cazul în care șirul inițial nu poate fi format, se va afișa $-1$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• $1 \leq K \leq 1 \ 000 \ 000$;
• Suma lungimilor celor $K$ șiruri $\leq 1 \ 000 \ 000$;
• Toate șirurile conțin doar litere mici ale alfabetului latin.

Exemplul 1

stdin

5
abcab
4
acde
bca
cab
aa

stdout

3

Explicație

Șirul abcab poate fi format folosind prefixele a, b, cab.

Exemplul 2

stdin

5
abcaz
4
acde
bca
cab
aa

stdout

-1

Explicație

Caracterul z nu se află în cele $4$ șiruri pe care le putem folosi.

Exemplul 3

stdin

5
aaaaa
2
a
aa

stdout

3

Explicație

Șirul aaaaa poate fi format folosind prefixele a, aa, aa.