Fișierul intrare/ieșire	traseu.in, traseu.out	Sursă	Olimpiada pe scoala 2015
Autor	clasică	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Traseu (clasele 11 și 12)

Sătul de atâtea olimpiade și concursuri, Algorel a plecat la munte, să se relaxeze. Odată ajuns acolo s-a hotărât să urmeze un traseu cu peisaje cât mai frumoase. El are la dispoziție o hartă codificată sub forma unei matrice cu M linii și N coloane, ale cărei elemente sunt numere naturale nenule reprezentând gradul de frumusețe corespunzător fiecărei zone (element al matricei). Algorel trebuie să plece din colțul stânga sus al matricei (poziția (1,1)) și să ajungă în colțul dreapta jos (poziția (M,N)), având voie să se deplaseze doar spre dreapta și în jos (de pe poziția curentă (i,j) se poate deplasa fie pe poziția (i+1,j), fie pe poziția (i,j+1)). Definim gradul de frumusețe al unui traseu ca fiind suma gradelor de frumusețe ale elementelor matricei care-l compun. Se cere găsirea gradului maxim de frumusețe pe care îl poate avea un traseu care respectă restricțiile de mai sus.

Date de intrare

Fișierul de intrare traseu.in conține pe prima linie două numere naturale nenule M și N. Pe următoarele M linii se află câte N numere naturale nenule, separate prin câte un spațiu, reprezentând elementele matricei A, care codifică harta.

Date de ieșire

În fișierul de ieșire traseu.out se va scrie un singur număr S reprezentând gradul maxim de frumusețe pe care îl poate avea un traseu care respectă restricțiile de mai sus. (Gradul de frumusețe al unui traseu este suma gradelor zonelor din matrice care îl compun.)

Restricții

• 1 ≤ M ≤ 500
• 1 ≤ N ≤ 500
• 1 ≤ A[i][j] ≤ 1000

Exemplu

Explicație

Traseul optim trece prin zonele (1,1), (1,2), (1,3), (2,3).