== include(page="template/taskheader" task_id="diagonale") ==

Se da o matrice patratica de dimenisune $NxN$. Se cere gasirea diagonalei de suma maxima. Prin diagonala, pe langa diagonala principala si cea secundara a matricei, ne vom referi la orice set de elemente situat pe o dreapta paralela cu una dintre acestea.

Se da o matrice patratica de dimenisune $NxN$. Se cere gasirea diagonalei de suma maxima. Prin diagonala intelegem orice set de elemente ce se afla pe o dreapta paralela cu diagonala principala sau cu cea secundara a matricei.

h2. Date de intrare

h2. Restricţii
* $1 ≤ N ≤ 1000$

* Elementele din matrice vor fi numere intregi mai mici ca $10^9^$ in modul
* Ati uitat-o pe Miruna.

* Elementele din matrice vor fi numere intregi mai mici ca 10^9^ in modul

h2. Exemplu

7391