Tina are o mică livadă cu copaci din specii diferite. Numărul acestora este m x n, iar poziţionarea lor este în centrul celulelor unei reţele cu m linii şi n coloane. Tina a sădit toţi copacii în aceeaşi zi. Fiecare copac, indiferent de specie, creşte cu câte 1 centimetru în fiecare zi în care nu este udat. În fiecare zi în care este udat, oricare copac creşte X centimetri. Se cunoaşte pentru fiecare copac situat pe linia i şi coloana j în livadă, înălţimea maximă hij pe care acesta poate să o atingă. Din momentul în care ajung la înălţimea maximă, copacii nu mai cresc şi nu depăşesc această înălţime, indiferent dacă mai sunt udaţi sau nu în zilele următoare. Înălţimile iniţiale ale copacilor se neglijează.
Tina nu este suficient de puternică pentru a căra multă apă într-o zi, motiv pentru care va uda cel mult un copac pe zi.
Cerinţă
Ajutaţi-o pe Tina să găsească o stratetegie potrivită pentru a uda livada, astfel încât toţi copacii să ajungă în timpul cel mai scurt la înălţimea maximă.
Date de intrare
Fişierul de intrare livada.in conţine pe prima linie trei numere naturale m n X. Pe fiecare dintre următoarele m linii se găsesc câte n numere naturale, reprezentând înălţimile maxime hij. Al j-lea număr de pe linia i+1 este hij.
Date de ieşire
Fişierul de ieşire livada.out va conţine o singură linie pe care se va scrie un număr natural Z, reprezentând numărul minim de zile necesare Tinei să-şi vadă toţi copacii din livadă ajunşi la înălţimile lor maxime.
Restricţii
1 < n, m <= 150
1 <= X <= 1000
1 <= h1 ... hn <= 10000
Orice copac poate fi udat de mai multe ori, în zile nu neaparat consecutive.
Exemple
livada.in
livada.out
Explicaţii
1 2 3
3 5
3
Copacul de înălţime 5 este udat cel puţin o zi. Dacă este udat o zi, atunci mai sunt necesare încă două zile pentru ca atât primul, cât şi al doilea copac să ajungă la înălţimea maximă
1 3 5
4 5 2
2
Tina udă câte o zi copacii de înălţimi maxime 4 şi 5 şi nu udă copacul de înaţime 2
2 2 4
2 3
4 5
3
Tina udă în prima zi copacul de înălţime 4, iar în a doua zi pe cel de înălţime 5. Mai este nevoie şi de a treia zi pentru ca pomul de înălţime maximă 3 să-şi atingă limita de creştere