* $1 ≤ N ≤ 50$
* $1 ≤ M ≤ 50$

* $1 ≤ K ≤ 12 000$
* Elementele matricii sunt numere intregi cuprinse in intervalul $[0, 100 000]$.

* $1 ≤ K ≤ 100 000$
* Elementele matricii sunt numere intregi cuprinse in intervalul $[0, 10 000]$.

* Se garanteaza ca pozitiile de start si de final sunt valide.
* Se garanteaza ca exista cel putin un drum valid de la pozitia de start la destinatie.

* In $20%$ din teste, $K = 1$.

* Pentru $50%$ din teste, $1 ≤ K ≤ 200$.

* Deplasarea se face in $4$ directii: sus, jos, stanga, dreapta.
* Laura trebuie sa se deplaseze intr-o casuta vecina in fiecare moment de timp.
* Drumul Laurei poate trece de mai multe ori prin aceeasi pozitie, caz in care trebuie considerata de mai multe ori valoarea din acea zona.

h2. Exemplu

3633