Problema lunii: drumeție

Pe o insulă se pot face drumeții, dar nu oricine poate ajunge oriunde. Se pleacă de la margine și se dorește atingerea unei altitudini cât mai mari.

Insula poate fi privită ca fiind o grilă cu M linii și N coloane. Pentru fiecare celulă a grilei este cunoscută altitudinea medie a zonei corespunzătoare (exprimată în metri),

Dintr-o anumită celulă se poate ajunge în oricare dintre celulele învecinate (pe orizontală sau verticală) dacă altitudinea medie a celulei în care se ajunge este cu cel mult K metri mai mare decât cea a celulei din care se pleacă. Dacă altitudinea medie este mai mică, trecerea este permisă.

Se poate porni din orice celulă a cărei altitudine este 0. Este garantat faptul că nu există celule cu altitudine 0 decât în jurul insulei.

Datele de intrare se citesc de la intrarea standard. Pe prima linie se vor afla valorile M, N și K, separate prin spații. Aceste valori sunt cuprinse între 1 și 1000. Fiecare dintre următoarele M linii va conține câte N numere, separate prin câte un spațiu, reprezentând altitudinile medii ale zonelor corezpunzătoare celulelor. Altitudinile medii sunt numere cuprinse între 0 și 8848.

Datele de ieșire se scriu la ieșirea standard; se va scrie un singur număr reprezentând altitudinea maximă la care se poate ajunge.

Exemplu

Intrare

Ieșire