Fişierul intrare/ieşire:	zmeu.in, zmeu.out	Sursă	ad-hoc
Autor	Cosmin Bondane	Adăugată de	Bondane Cosmin •cos_min
Timp execuţie pe test	0.05 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 matrici: A si B, de dimensiuni NxN. 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.

Date de intrare

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.

Date de iesire

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

Restrictii

• 1 ≤ P ≤ 500
• 1 ≤ N ≤ 100
• 0 ≤ valoarea elementelor matricei A ≤ P
• 0 ≤ valoarea elementelor matricei B ≤ 10⁹
• A[1][1] = A[N][N] = B[1][1] = B[N][N] = 0

Exemplu

Cum se trimit solutii?