Rover

NASA plănuiește o nouă misiune Rover pe Marte în anul 2020. Principalul obiectiv al acestei misiuni este de a determina, cu ajutorul unui nou Rover, dacă a existat în trecut viață pe Marte. Până când va fi lansată misiunea, Roverul este supus la tot felul de teste în laboratoarele NASA. Într-unul din teste, Roverul trebuie să parcurgă o suprafață de forma unui caroiaj cu $N$ linii și $N$ coloane. Acesta pornește din zona de coordonate $(1,1)$ și trebuie să ajungă în zona de coordonate $(N,N)$, la fiecare pas putându-se deplasa din zona în care se află într-una din zonele învecinate la nord, sud, est sau vest. Pentru fiecare zonă de coordonate $(i,j)$ se cunoaște $A_{ij}$, stabilitatea terenului din acea zonă. Știind că Roverul are o greutate $G$, o zonă cu stabilitatea terenului cel puțin egală cu $G$ se consideră o zonă sigură pentru deplasarea Roverului, iar o zonă cu stabilitatea terenului mai mică decât $G$ se consideră o zonă periculoasă pentru Rover.

Cerințe

1. Determinați numărul minim posibil de zone periculoase pe care le traversează Roverul pentru a ajunge din zona $(1,1)$ în zona $(N,N)$.
2. Determinați greutatea maximă pe care o poate avea un Rover care să ajungă din zona $(1,1)$ în zona $(N,N)$, fără a traversa nicio zonă periculoasă pentru el.

Date de intrare

Pe prima linie a fișierului de intrare rover.in se găsește numărul natural $V$ a cărui valoare poate fi doar $1$ sau $2$. Dacă $V$ este $1$, pe a doua linie a fișierului de intrare se găsesc două numere naturale $N$ și $G$ cu semnificația din enunț, iar dacă $V$ este $2$, pe a doua linie a fișierului de intrare se află doar numărul $N$.
Pe următoarele $N$ linii se află câte $N$ numere $A_{i,j}$, reprezentând stabilitatea terenului din zona $(i,j)$.

Date de ieșire

Fișierul de ieșire este rover.out.

Dacă valoarea lui $V$ este $1$, atunci fișierul de ieșire va conține pe prima linie un număr natural reprezentând numărul minim de zone periculoase pe care trebuie să le traverseze Roverul de greutate $G$.

Dacă valoarea lui $V$ este $2$, atunci fișierul de ieșire va conține pe prima linie un număr natural reprezentând greutatea maximă a unui Rover care poate ajunge din zona $(1,1)$ în zona $(N,N)$ fără a traversa zone periculoase pentru el.

Restricții și precizări

• $1 \leq N \leq 500$
• $1 \leq G \leq 5 \ 000$
• $1 \leq A_{ij} \leq 10 \ 000$
• Zonele de coordonate $(1,1)$ și $(N,N)$ nu sunt zone periculoase pentru Rover.
• Roverul nu va trece de mai multe ori prin aceeași zonă.

Exemplul 1

rover.in

1
5 5
5 1 3 4 7
5 2 1 8 5
2 9 5 3 3
4 1 1 1 9
5 1 6 1 8

rover.out

3

Explicație

Numărul minim de zone periculoase traversate de la poziția $(1,1)$ până la poziția $(5,5)$ este $3$.

Un traseu posibil este:

Figura 1 din enunțul original al problemei Rover.Mărește schema ↗

Exemplul 2

rover.in

2
5
5 1 3 4 7
5 2 1 8 5
2 9 5 3 3
4 1 1 1 9
5 1 6 1 8

rover.out

2

Explicație

Greutatea maximă a unui Rover care poate ajunge din zona $(1,1)$ în zona $(5,5)$ fără a trece prin zone periculoase pentru el este $2$.

Un traseu posibil este:

Figura 2 din enunțul original al problemei Rover.Mărește schema ↗