* $1 ≤ $N$ , $M$ ≤ 800$
* $0 ≤ $D$ ≤ 100000 $

* $0 ≤ $A(i,j)$ ≤ 100000 $ , ∀ $1 ≤ i ≤ N $ , $1 ≤ j ≤ M$

* $0 ≤ $A(i,j) ≤ 100000 $ , ∀ $1 ≤ i ≤ N $ , $1 ≤ j ≤ M$

* Destinatia finala poate sa coincida cu punctul de plecare. Un drum format dintr-un singur patratel este considerat valid.

Pentru patratelele de inaltime $7$ destinatia finala poate fi orice patratel de inaltime $7$ si patratelul de inaltime $10$.
Pentru patratelele de inaltime $3$ destinatia finala poate fi orice patratel.
Pentru patratelul de inaltime $5$ destinatia finala poate fi orice patratel mai putin cele de inaltime $3$.

Pentru patratelul de inaltime $6$ destinatia finala poate fi doar el insusi (nu poate trece prin patratelele de inaltime $3$ datorita primei restrictii)

Pentru patratelul de inaltime $6$ destinatia finala poate fi doar el însusi (nu poate trece prin patratelele de inaltime $3$ datorita primei restrictii)

Pentru patratelul de inaltime $10$ destinatia finala poate fi doar el insusi.