== include(page="template/taskheader" task_id="edist") ==

Poveste şi cerinţă...

Fie un şir oarecare de caractere. Asupra lui definim urmatoarele 3 operatii:
 
* *inserare*: pe o poziţie oarecare se poate insera un caracter oarecare
* *ştergere*: se sterge caracterul de pe o pozitie oarecare din sir
* *inlocuire*: se inlocuieste caracterul de pe o pozitie oarecare din sir cu orice alt caracter.
 
Se dau doua siruri $S_1_$ si $S_2_$ continand doar litere mici ale alfabetului englez avand $N$ si, respectiv, $M$ caractere. Distanta de editare a celor doua siruri este numarul minim de operatii definite mai sus ce trebuie aplicat asupra primului sir pentru a-l transforma in cel de-al doilea sir. Acelasi tip de operatie poate fi aplicat de mai multe ori. Aflati distanta de editare a celor doua siruri, stiind ca aceasta este mai mica sau egala cu un numar intreg $K$ dat.

h2. Date de intrare

Fişierul de intrare $edist.in$ ...

Pe prima linie a fişierului de intrare $edist.in$ se afla trei numere intregi: $N$, $M$ si $K$. Pe a doua linia a fisierului se afla $N$ litere mici din alfabetul englez reprezentand sirul $S_1_$. Pe a treia linie a fisierului se afla $M$ litere mici din alfabetul englez ce reprezinta sirul $S_2_$.

h2. Date de ieşire

În fişierul de ieşire $edist.out$ ...

În fişierul de ieşire $edist.out$ se va afla un singur numar intreg reprezentand distanta de editare a celor doua siruri.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 20 000$
* $1 ≤ K ≤ 500$
* Pentru 70% din teste, N ≤ 2 000$.

h2. Exemplu

h3. Explicaţie

...

O posibila modalitate de a transforma sirul $harpa$ in $armura$ folosind $4$ operatii este:
 
1. stergem litera $h$ din primul sir,
2. inlocuim litera $p$ cu litera $m$,
3. adaugam litera $u$ inainte de ultima litera din primul sir,
4. adaugam litera $r$ inainte de ultima litera din primul sir.

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