mesaj

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.

h2. 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.
h2. Date de intrare

h2. Restrictii
* $5 ≤ N ≤ 1 000$

* $1 ≤ M ≤ 1.600$

* $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}$

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

1681