Zmeu

zmeu

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

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$ matrice: $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. Datorita terenului foarte greu, Farfurel se poate deplasa doar la sud si la est. Stiind ca pericolul se conserva si ca Farfurel poate ajunge hrana zmeului(daca pericolul acumulat de el depaseste o valoare $P$), ajutati-l pe eroul nostru aflat in pozitia ({$1$},{$1$}) sa ajunga la Sarah aflata in pozitia ({$N$},{$N$}) cu cat mai putini bani posibil.

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

Pe prima linie a fisierului de intrare se gasesc doua numre intregi $N$ si $P$ cu semnficatiile de mai sus. Pe urmatoarele {$N$} linii se regasesc cate $N$ numere intregi care descriu matricea $A$. Pe urmatoarele {$N$} linii se regasesc cate $N$ numere intregi care descriu matricea $B$.

Pe prima linie a fisierului de intrare se gasesc doua numre intregi $N$ si $P$, numarul de linii si coloane a matricelor $A$ si $B$, respectiv pericolul maxim admis. Pe urmatoarele $2$*{$N$} linii se regasesc cate $N$ numere intregi care descriu matricea $A$, respectiv matricea $B$.

h2. Date de iesire

Pe singura linie a fisierului de iesire se va afisa suma minima necesara lui Farfurel sa isi indeplineasca misiunea.

Pe singura linie a fisierului de intrare se va afisa suma minima necesara lui Farfurel sa isi indeplineasca misiunea.

h2. Restrictii

* $1$ ≤ $P$ ≤ $500$
* $2$ ≤ $N$ ≤ $100$
* $0$ ≤ $A${~i,j~} ≤ $P$
* $0$ ≤ $B${~i,j~} ≤ $10^9^$
* $A${~1,1~} = $A${~N,N~} = $B${~1,1~} = $B${~N,N~} = $0$
* Rezultatul se incadreaza pe 32 de biti

* $1$ ≤ P ≤ $500$
* $1$ ≤ N ≤ $100$
* $0$ ≤ valoarea elementelor matricei A ≤ $P$
* $0$ ≤ valoarea elementelor matricei B ≤ $10^9^$
* {$A$}[{$1$}][{$1$}] = {$A$}[{$N$}][{$N$}] = {$B$}[{$1$}][{$1$}] = {$B$}[{$N$}][{$N$}] = $0$

h2. Exemplu
table(example). |_. zmeu.in |_. zmeu.out |

| 4 6
0 2 3 4
1 2 2 2
4 1 3 2
1 4 3 0
0 2 2 1
4 1 2 1
3 3 4 4
5 1 3 0
| 2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

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

h3. Explicatie
...
== include(page="template/taskfooter" task_id="zmeu") ==

2611