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

Fie un şir oarecare de caractere. Asupra lui definim urmatoarele 3 operatii:

Fie un şir oarecare de caractere. Asupra lui definim următoarele 3 operaţii:

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

* *inserare*: pe o poziţie oarecare se adauga un caracter oarecare
* *ştergere*: se şterge caracterul de pe o poziţie oarecare din şir
* *înlocuire*: se înlocuieşte caracterul de pe o poziţie oarecare din şir cu orice alt caracter.

Se dau doua siruri $S1$ si $S2$ 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.

Se dau două şiruri $S1$ si $S2$ conţinând doar litere mici ale alfabetului englez şi având $N$ şi, respectiv, $M$ caractere. Distanţa de editare a celor două şiruri este numărul minim de operaţii definite mai sus ce trebuie aplicat asupra primului şir pentru a-l transforma în cel de-al doilea şir. Acelaşi tip de operaţie poate fi aplicat de mai multe ori. Aflaţi distanţa de editare a celor doua şiruri, ştiind că aceasta este mai mică sau egală cu un număr întreg $K$ dat.

h2. Date de intrare

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 $S1$. Pe a treia linie a fisierului se afla $M$ litere mici din alfabetul englez ce reprezinta sirul $S2$.

Pe prima linie a fişierului de intrare $edist.in$ se afla trei numere întregi: $N$, $M$ şi $K$. Pe a doua linia a fişierului se află $N$ litere mici din alfabetul englez reprezentând şirul $S1$. Pe a treia linie a fişierului se află $M$ litere mici din alfabetul englez ce reprezintă şirul $S2$.

h2. Date de ieşire

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

În fişierul de ieşire $edist.out$ se va afla un singur număr întreg reprezentând distanţa de editare a celor doua şiruri.

h2. Restricţii

* $1 ≤ N ≤ 20 000$

* $1 ≤ N, M ≤ 20 000$

* $1 ≤ K ≤ 500$

* Pentru 70% din teste, N ≤ 2 000$.

* Pentru $70%$ din teste $N, M ≤ 2 000$.

h2. Exemplu

| 5 6 5
harpa
armura

| 4
|

| 4 |
| 5 5 4
carte
antet
| 3
|

h3. Explicaţie

O posibila modalitate de a transforma sirul $harpa$ in $armura$ folosind $4$ operatii este:

O posibilă modalitate de a transforma şirul $harpa$ în $armura$ folosind $4$ operaţii 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.

1. ştergem litera $h$ din primul şir,
2. înlocuim litera $p$ cu litera $m$,
3. adăugăm litera $u$ înainte de ultima literă din primul şir,
4. adăugăm litera $r$ înainte de ultima literă din primul şir.

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

6121