lant

Ion este un lingvist pasionat. Recent el a descoperit un text scris într-o limbă necunoscută. Textul este scris pe mai multe linii şi este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spaţii sau/şi semne de punctuaţie (,:;.!?-).

Ion a fost frapat că există multe similitudini între cuvintele din text. Fiind foarte riguros, Ion defineşte similitudinea a două cuvinte după cum urmează.

Fie $c_1$ şi $c_2$ două cuvinte. Cuvântul $c_1$ poate fi obţinut din cuvântul $c_2$ printr-o succesiune de operaţii elementare. Operaţiile elementare ce pot fi folosite sunt:

• ștergerea unui caracter
• inserarea unui caracter
• modificarea unui caracter

Definim similitudinea dintre $c_1$ şi $c_2$ ca fiind numărul minim de operaţii aplicate cuvântului $c_1$ pentru a ajunge la cuvântul $c_2$.

Fie $c_0$ primul cuvânt din text. Începând cu $c_0$ putem construi lanţuri de $k$-similitudine.

Un lanţ de $k$-similitudine este o succesiune de cuvinte distincte din text cu următoarele proprietăţi:

• dacă cuvântul $x$ apare în lanţ înaintea cuvântului $y$, atunci prima apariţie a lui $x$ în text precedă prima apariţie a lui $y$ în text;
• dacă $x$ şi $y$ sunt cuvinte consecutive în lanţ (în ordinea $x\ y$) , atunci similitudinea dintre $x$ şi $y$ este $≤k$;
• lanţul este maximal (adică nu putem adăuga încă un cuvânt la sfârşitul acestui lanţ, astfel încât să fie respectate proprietăţile precedente).

Două lanțuri de $k$-similitudine sunt diferite dacă au lungimi diferite sau dacă există o poziție unde cuvintele din cele două lanțuri sunt diferite.

Cerinţă

Scrieţi un program care să determine numărul de lanţuri de $k$-similitudine care încep cu $c_0$.

Date de intrare

Fişierul de intrare lant.in conţine pe prima linie valoarea $k$. Pe următoarele linii se află textul dat.

Date de ieşire

Fişierul de ieşire lant.out va conţine o singură linie pe care va fi scris numărul de lanţuri de $k$-similitudine care încep cu $c_0$.

Restricţii

• Lungimea unei linii din text nu depăşeşte $1\ 000$ de caractere.
• Lungimea unui cuvânt nu depăşeşte $30$ de caractere.
• Numărul total de cuvinte $≤ 150$.
• Pentru datele de test, numărul de lanţuri de $k$-similitudine care încep cu $c_0$ va fi $≤ 2\ 000\ 000\ 000$.
• Enunțul a fost modificat

Exemplu

lant.in

5
ana are mere, banane,
pere si castane.

lant.out

6

Explicații

Lanţurile de $5$-similitudine care se pot forma sunt:
ana are mere pere
ana are pere
ana are banane castane
ana are si
ana banane castane
ana si