Tassadar a supravieţuit cursului de Kultură şi Civilizaţie, dar a rămas profund afectat de această experienţă şi este convins că, de fapt, cursurile erau incoerente.

Pentru a verifica acest lucru, el a întocmit un dicţionar care cuprinde toate cuvintele incoerente pe care le-a întâlnit de-a lungul vieţii. Gradul de incoerenţă al unui cuvânt din dicţionar este egal cu lungimea cuvântului. Cursul de Kultură şi Civilizaţie poate fi reprezentat printr-un şir de N litere mici ale alfabetului latin.

Pentru a verifica acest lucru, el a întocmit un dicţionar care cuprinde toate cuvintele incoerente pe care le-a întâlnit de-a lungul vieţii. Gradul de incoerenţă al unui cuvânt din dicţionar este egal cu lungimea cuvântului. Cursul de Kultură şi Civilizaţie poate fi reprezentat printr-un şir de $N$ litere mici ale alfabetului latin.

Tassadar vrea să insereze spaţii în curs şi să delimiteze, astfel, cuvintele care apar în acesta. El doreşte să facă acest lucru astfel încât suma gradelor de incoerenţă ale cuvintelor din curs să fie maximă.

h2. Date de intrare

Fişierul de intrare kc.in conţine pe prima linie numerele N şi K, reprezentând lungimea cursului, respectiv numărul de cuvinte din dicţionar. Pe următoarea linie se află un şir de N litere, reprezentând cursul de Kultură şi Civilizaţie. Pe următoarele K linii se vor afla cuvintele din dicţionar, câte unul pe linie.

Fişierul de intrare $kc.in$ conţine pe prima linie numerele $N$ şi $K$, reprezentând lungimea cursului, respectiv numărul de cuvinte din dicţionar. Pe următoarea linie se află un şir de $N$ litere, reprezentând cursul de Kultură şi Civilizaţie. Pe următoarele $K$ linii se vor afla cuvintele din dicţionar, câte unul pe linie.

h2. Date de ieşire

Fişierul de ieşire kc.out va conţine pe prima linie suma maximă a gradelor de incoerenţă care se poate obţine prin delimitarea cuvintelor din curs cu spaţii.

Fişierul de ieşire $kc.out$ va conţine pe prima linie suma maximă a gradelor de incoerenţă care se poate obţine prin delimitarea cuvintelor din curs cu spaţii.

h2. Restricţii

* 1 ≤ N ≤ 100 000
* 1 ≤ K ≤ 100 000
* 1 ≤ L ≤ 100 000, unde L este suma lungimilor cuvintelor din dicţionar

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ 100 000$
* $1 ≤ L ≤ 100 000$, unde $L$ este suma lungimilor cuvintelor din dicţionar

* Un cuvânt este o subsecvenţă maximală de litere mici ale alfabetului latin şi este delimitat la stânga şi la dreapta fie de un spaţiu, fie de începutul cursului, fie de sfârşitul cursului

* Dacă un cuvânt din curs nu apare în dicţionar, acesta are gradul de incoerenţă 0
* Pentru teste în valoare de 8 puncte, N ≤ 1000 şi L ≤ 1000
* Pentru teste în valoare de alte 16 de puncte, N ≤ 1000

* Dacă un cuvânt din curs nu apare în dicţionar, acesta are gradul de incoerenţă $0$
* Pentru teste în valoare de $10$ puncte, $N ≤ 1000$ şi $L ≤ 1000$
* Pentru teste în valoare de alte $30$ de puncte, $N ≤ 1000$

h2. Exemplu

h3. Explicaţie

Există patru moduri în care putem delimita cuvintele din curs cu spaţii: ”abc” (conţine un singur cuvânt cu gradul de incoerenţă 3), ”ab c” (conţine un cuvânt cu gradul de incoerenţă 0 şi unul cu gradul de incoerenţă 1), ”a bc” (conţine un cuvânt cu gradul de incoerenţă 1 şi unul cu gradul de incoerenţă 0) şi ”a b c” (conţine două cuvinte cu gradul de incoerenţă 1 şi unul cu gradul de incoerenţă 0). Dintre toate aceste modalităţi, este optim să nu inserăm niciun spaţiu în curs, pentru a obţine suma gradelor de incoerenţă maximă, aceasta fiind egală cu 3.

Există patru moduri în care putem delimita cuvintele din curs cu spaţii: $"abc"$ (conţine un singur cuvânt cu gradul de incoerenţă $3$), $"ab c"$ (conţine un cuvânt cu gradul de incoerenţă $0$ şi unul cu gradul de incoerenţă $1$), $"a bc"$ (conţine un cuvânt cu gradul de incoerenţă $1$ şi unul cu gradul de incoerenţă $0$) şi $"a b c"$ (conţine două cuvinte cu gradul de incoerenţă $1$ şi unul cu gradul de incoerenţă $0$). Dintre toate aceste modalităţi, este optim să nu inserăm niciun spaţiu în curs, pentru a obţine suma gradelor de incoerenţă maximă, aceasta fiind egală cu $3$.

== include(page="template/taskfooter" task_id="kc") ==