Rezolvare PBinfo #4576

Bilbo Baggins a reușit să intre în Muntele Singuratic. În Muntele Singuratic este o rețea de n galerii numerotate de la 1 la n, fiecare galerie fiind împărțită în m camere numerotate de la 1 la m. Bilbo găsește o hartă a acestor galerii și vede că în fiecare din cele n*m camere se află o cantitate de aur. Bilbo a intrat prin prima cameră a primei galerii și conform hărții poate iesi doar prin ultima cameră a primei galerii.

Dintr-o cameră numerotatată (i,j) Bilbo se poate strecura fără a fi detectat de către Smaug doar în camerele numerotate cu (i-1,j+1), (i,j+1) și (i+1,j+1) fără a putea părăsi rețeaua de galerii decât prin camera (1,m).

Să se determine cantitatea maximă de aur pe care o poate colecta Bilbo din Muntele Singuratic.

Cerința

Să se scrie un program care citește două numere naturale n și m și apoi de pe n linii căte m numere naturale reprezentând cantitatea de aur din fiecare cameră din Muntele Singuratic și care calculează și afișează cantitatea maximă de aur pe care o poate colecta Bilbo.

Date de intrare

Fișierul de intrare bilbob.in conține pe prima linie numerele n și m. Fiecare dintre următoarele n linii conține câte m numere, reprezentând cantitatea de aur din fiecare cameră.

Date de ieşire

Fișierul de ieșire bilbob.out va conține pe prima linie numărul S, reprezentând maximă de aur pe careo poate obține Bilbo.

Restricții și precizări

• 2 ≤ n,m ≤ 200
• cantitatea de aur din fiecare cameră este mai mică decât 1000

Exemplu:

bilbob.in

4 5
5 8 3 1 7
1 1 4 5 1
5 8 9 1 7
5 8 6 6 9

bilbob.out

29

Explicație

Suma 29 se poate obține adunând numerele:
5 8 3 1 7
1 1 4 5 1
5 8 9 1 7
5 8 6 6 9