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;

Cerința

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 ≤ 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.

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.