Se dau L şi C două numere naturale şi o matrice cu L linii şi C coloane având elementele numere întregi. Trebuie alese elemente care să respecte următoarele proprietăţi:
- de pe fiecare linie se alege o secvenţă de elemente aflate pe coloane cu indici consecutivi, începând cu elementul de pe prima coloană;
- pentru orice două linii consecutive, lungimile secvenţelor alese trebuie să difere prin 1 sau să fie egale;
- nu trebuie să existe 3 linii consecutive pentru care lungimile secvenţelor alese să fie egale, sau să fie în ordine strict crescătoare sau strict descrescătoare;
Exemple de alegeri invalide pentru o matrice 4X4:
Exemple de alegeri valide pentru o matrice 4X4
Cerinţă
Se cere să se facă o alegere a secvenţelor de pe fiecare linie a matricei respectând restricţiile precizate, astfel încât însumând elementele acestora să se obţină suma maximă posibilă.
Date de intrare
Prima linie a fişierului left.in conţine două numere naturale sunt L şi C separate printr-un spaţiu reprezentând în ordine numărul de linii şi numărul de coloane ale matricei date. Pe fiecare dintre următoarele L linii sunt câte C numere întregi, separate prin câte un spaţiu, reprezentând elementele matricei.
Date de ieşire
Prima linie a fişierului left.out va conţine un singur număr întreg, reprezentând suma maximă cerută.
Restricţii
2 <= L, C <= 1000
Valorile din matrice sunt numere întregi pe 32 de biţi.
Rezultatul este un număr întreg pe 32 de biţi.
Suma elementelor oricărei submatrice este un număr întreg pe 32 de biţi.
Exemple
left.in
left.out
Explicaţii
3 3
1 2 3
1 2 -1
-1 2 -2
10
De pe prima linie se aleg 3 numere, iar de pe celelalte linii câte 2 numere.
