Rezolvare PBinfo #1805

Hamsterul Rufus pleacă în expediție. Ajuns într-un câmp luminat, de forma unei matrice A cu N linii și M coloane, o zărește în depărtare pe prietena sa, Rufia. Acesta își dorește să ajungă cât mai repede la ea, dar, în același timp, să nu-și neglijeze capacitatea fizică.

Rufus pleacă din punctul de linie 1 și coloană 1 al matricei, iar Rufia îl asteaptă în punctul de linie N și coloană M. Fiind un teren accidentat, acesta consumă o anumită energie și un anumit timp pentru a ajunge dintr-un punct în unul din cele maxim 8 puncte vecine ale sale, cu condiția să rămână în interiorul spațiului bine delimitat.

Energia consumată pentru a ajunge în punctul de linie i și coloană j din unul din punctele sale vecine este dată de valoarea lui | A[i][j] | (valoarea lui A[i][j] în modul ), iar timpul consumat pentru a ajunge în acest punct dintr-un punct vecin este dat de valoarea T[i][j]. Există precizarea că în punctul de linie i și coloană j, dacă A[i][j] < 0, atunci în acest punct Rufus poate să își recapete toată capacitatea fizică avută inițial.

Cerința

Ajutați-l pe Rufus să ajungă la prietena sa Rufia în cel mai scurt timp posibil și găsiți, de asemenea,capacitatea fizică inițială minimă, știind că aceasta poate fi cel mult K. Dacă nu există un drum pentru care Rufus sa ajungă la destinație, să se afișeze Nu exista drum.

Date de intrare

Fișierul de intrare expeditie.in conține pe prima linie numerele N, M și K, cu specificațiile din enunț.

De pe următoarele N linii se vor citi câte M numere, elementele matricei A.
Următoarele N linii vor avea tot câte M numere, elementele matricei T.

Date de ieșire

Fișierul de ieșire expeditie.out va conține pe prima linie un număr reprezentând timpul minim pentru a ajunge la destinație, iar pe cea de-a doua linie capacitatea fizică minimă necesară pentru a ajunge în acest timp.

Restricții și precizări

• 1 ≤ N, M ≤ 30
• 1 ≤ K ≤ 500
• a[i][j] ≤ 500
• 1 ≤ T[i][j] ≤ 100
• Pentru 20% din teste K = 1
• Pentru 50% din teste K <= 100

Exemplu:

expeditie.in

3 3 5
1 1 3
0 5 2
3 -4 2
1 1 1
1 5 2
1 2 3

expeditie.out

6
4

Explicație

Drumul ales va fi 1,1 ->2,1 ->3,2 ->3,3, drum ce îi va lua lui Rufus un timp egal cu | t[2][1] | + |t[3][2]| + | t[3][3] | = 6, acesta fiind timpul minim, capacitate fizică inițială fiind egală cu 4.