left

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 $4 \cdot 4$:

Exemple de alegeri valide pentru o matrice $4 \cdot 4$

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 și precizări

• $2 \leq L, C \leq 1 \ 000$
• 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.

Exemplu

left.in

3 3
1 2 3
1 2 -1
-1 2 -2

left.out

10

Explicație

De pe prima linie se aleg $3$ numere iar de pe celelalte linii câte $2$ numere.