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

Farfurel si-a gasit in sfarsit iubirea, pe Liaiu. Din pacate aceasta este inchisa intr-un turn si este pazita de zmeul cel rau. Farfurel a reusit sa faca rost de harta spre turn, insa bugetul sau este limitat.
Harta este codificata sub forma a $2$ matrici ({$A$} si {$B$}) cu $N$ linii si $N$ coloane. Valoarea pozitiei ({$i$},{$j$}) din prima matrice reprezinta gradul de pericol daca Farfurel s-ar deplasa in aceasta pozitie. Valoarea pozitie ({$i$},{$j$}) din a doua matrice reprezinta costul ca pozitia respectiva sa aiba pericolul nul. Pozitia de start a eroului nostru este in pozitia ({$1$},{$1$}), iar pozitia unde este tinuta Liaiu este ({$N$},{$N$}). Farfurel se poate deplasa doar in sud sau est. Pericolul se conserva(se aduna din vecini), iar acesta nu poate depasi o valoare $P$, deoarece Farfurel ar fi mancat de zmeu.
Ajuta-l pe Farfurel sa ajunga la Liaiu cu cat mai putini bani.
 

Farfurel si-a gasit in sfarsit iubirea, pe Sarah. Din pacate aceasta este inchisa intr-un turn si este pazita de zmeul cel rau. Cheltuind foarte multi bani, Farfurel a reusit sa faca rost de harta spre turn. Harta este codificata sub forma a $2$ matrici: $A$ si $B$, de dimensiuni {$N$}x{$N$}. Valoarea pozitiei ({$i$},{$j$}) a matricei $A$ reprezinta gradul de pericol pentru ca Farfurel sa ajunga in pozitia respectiva. Valoarea pozitie ({$i$},{$j$}) a matricei $B$ reprezinta costul ca pozitia respectiva sa aiba pericolul nul. Stiind ca pericolul se conserva, iar daca acesta depaseste o valoare $P$, Farfurel devine hrana zmeului. Ajutati-l pe Farfurel aflat in pozitia ({$1$},{$1$}) sa ajunga la Sarah aflata in pozitia ({$N$},{$N$}) cu cat mai putini bani posibil.

h2. Date de intrare

h2. Restrictii

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

* $1$ ≤ P ≤ $100$
* $1$ ≤ N ≤ $100$
* $0$ ≤ elementele matricei A ≤ $P$
* $0$ ≤ elementele matricei B ≤ $1000$
* {$A$}[{$1$}][{$1$}] = {$A$}[{$N$}][{$N$}] = {$B$}[{$1$}][{$1$}] = {$B$}[{$N$}][{$N$}] = 0
 

h2. Exemplu