== 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$ 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.
h2. Date de intrare
Fisierul de intrare $zmeu.in$ ...
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$.
h2. Date de iesire
In fisierul de iesire $zmeu.out$ ...
Pe singura linie a fisierului de iesire 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
h2. Exemplu
table(example). |_. zmeu.in |_. zmeu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicatie
== include(page="template/taskfooter" task_id="zmeu") ==
...
== include(page="template/taskfooter" task_id="zmeu") ==
