Lui OMan îi place viteza, aşa că s-a dus la schi! Pârtia este de formă pătrată şi este împărţită în n x n pătrate egale numerotate de la stânga la dreapta şi de sus în jos cu numere de la 1 la n.
Fiecare pătrăţel are asociată o anumită înălţime exprimată în milimetri. OMan pleacă din pătratul de coordonate (1, 1) cu viteza iniţială 1 şi trebuie să ajungă în pătratul de coordonate (n, n) cu viteză maximă. Aflându-se într-un pătrat de coordonate (i, j), OMan poate trece fie în pătratul din sud, adică de coordonate (i+1, j), fie în pătratul de la est, adică de coordonate (i, j+1). La fiecare pas, dacă pătratul în care se află are înălţimea x iar pătratul vecin are înălţimea y, atunci viteza sa creşte cu x – y (dacă x >= y), sau scade cu y – x (dacă x < y). Mai mult, dacă pasul curent schimbă direcţia faţă de direcţia de la pasul anterior, atunci viteza cu care ajunge în pătratul vecin se înjumătăţeşte (se obţine câtul împărţirii la 2).
De exemplu, presupunem că OMan a ajuns din (2, 5) în (3, 5) (deci mergând pe direcţia sud) cu viteza de 10 şi pătratul (3, 5) are înălţimea 8. Acum OMan se deplasează spre est, deci în pătratul (3, 6) de înălţime 5. Atunci înseamnă că a schimbat direcţia şi viteza sa în pătratul (3, 6) este (10+8–5)/2 = 6. Evident, OMan nu se poate deplasa cu viteză negativă sau zero.
Cerinţă
Scrieţi un program care determină viteza maximă pe care o poate obţine OMan în pătratul de coordonate (n, n) plecând din pătratul de coordonate (1,1) cu viteza iniţială 1.
Date de intrare
Fişierul speed.in conţine pe prima linie numărul natural n, iar pe următoarele n linii şi n coloane sunt date înălţimile celor n x n pătrate ale pârtiei.
Date de ieşire
Fişierul speed.out va conţine un singur număr natural reprezentând viteza maximă.
Restricţii
2 <= n <= 300
înălţimile pătratelor sunt numere naturale cuprinse între 0 şi 1000
Dacă OMan nu poate ajunge în poziţia (n, n) datorită vitezei mai mici sau egale cu 0, atunci în fişier se va afişa valoarea 0
Din poziţia (1,1) OMan se poate deplasa în ambii vecini de la est şi sud fără a se considera că schimbă direcţia.
Exemplu
speed.in
speed.out
Explicaţii
3
9 8 6
9 5 2
7 1 1
5
Traseul care îi dă viteză maximă este:
din (1,1) în (1,2) – viteză 1+(9–8)=2
din (1,2) în (1,3) – viteză 2+(8–6)=4
din (1,3) în (2,3) – viteză (4+5–1)/2=4 (a schimbat direcţia)
din (2,3) în (3,3) – viteză 4+(2–1)=5.
