== include(page="template/taskheader" task_id="traseu") ==
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)$). Se cere găsirea sumei maxime a gradelor de frumusețe pe care o poate avea un traseu care respectă restricțiile de mai sus.
Sătul de atâtea olimpiade și concursuri, Algorel a plecat la munte, să se relaxeze. Odată ajuns 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. Algorel trebuie să plece din colțul stânga sus al matricei (poziția (1,1)) și să ajungă în colțul dreapta jos
h2. 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.
Fișierul de intrare $traseu.in$ ...
h2. 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.)
În fișierul de ieșire $traseu.out$ ...
h2. Restricții
* $1 ≤ M ≤ 500$
* $1 ≤ N ≤ 500$
* $1 ≤ A[i][j] ≤ 1000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. traseu.in |_. traseu.out |
| 2 3
1 10 20
11 2 3
| 34
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
