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).

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