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

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise

Traseu (clasele 11-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).