Fişierul intrare/ieşire:	mesaj.in, mesaj.out	Sursă	Stelele Informaticii 2006, clasele 9-10
Autor	Mircea Bogdan Pasoi	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.075 sec	Limită de memorie	20096 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Mesaj

Zaharel ii trimite mesaje prietenei sale Eugenia folosind un sistem propriu de comunicatii (ca sa nu dea banii pe SMS-uri). Din pacate, sistemul lui Zaharel nu este complet eficient, iar uneori mesajul este distorsionat, mai exact este posibil sa apara caractere in plus in mesaj. Din fericire, vocabularul lui Zaharel este relativ limitat, iar Eugenia stie de profite de acest lucru: a facut o lista cu toate cele N cuvinte pe care le poate folosi Zaharel in cadrul mesajului. Sistemul lui Zaharel nu foloseste spatii pentru despartirea cuvintelor, dar Eugenia este destul de isteata sa-si dea seama intelesul mesajului, chiar si fara spatii.

Cerinta

Stiind lista de N cuvinte precum si mesajul final format din M caractere, aflati numarul minim de caractere pe care Eugenia trebuie sa le elimine din mesaj pentru ca acesta sa poate fi reprezentat ca o secventa de cuvinte din dictionar.

Date de intrare

Pe prima linie a fisierului mesaj.in se afla doua numere naturale N si M reprezentand numarul de cuvinte din lista si lungimea mesajului. Pe linia a doua se vor afla M caractere reprezentand mesajul. Urmatoarele N linii contin cate un cuvant din lista.

Date de iesire

Fisierul de iesire mesaj.out va contine o singura linie pe care se va afla numarul minim de caractere care trebuie sterse.

Restrictii

• 5 ≤ N ≤ 1 000
• 1 ≤ M ≤ 1 600
• Cuvintele din lista au lungimi cuprinse intre 1 si 20
• Mesajul si cuvintele sunt formate doar din litere mici din alfabetul englez {a, b, c ... z}
  

Exemplu

Explicatie

carmrcmddrcaddamroom
Daca se elimina litere de culoare rosie, mesajul ramas va reprezenta urmatoare insiruire de cuvinte din lista:
car | mr | cdr | cadar | oom

Cum se trimit solutii?