Trafalet

David este mare zugrav și nu se duce nicăieri fără trafaletul său magic. El are la dispoziție o matrice $A$ cu $N$ linii și $M$ coloane, care este colorată în alb și negru, asemenea unei table de șah. Fiecare celulă a matricei conține o valoare asociată.

David vopsește o submatrice cu alb sau negru la alegere. Trafaletul adună automat (pentru că este magic) valorile din celulele vopsite care nu își schimbă culoarea, și scade valorile din celulele vopsite care își schimbă culoarea. Rezultatul acestui calcul este punctajul lui David.

O submatrice a unei matrice $A$ cu $N$ linii și $M$ coloane este descrisă de două celule din matrice, colțul stânga-sus $(l_1,c_1)$ și colțul dreapta-jos $(l_2,c_2)$ al submatricei. Submatricea conține elementele $A[l][c]$ pentru $1 \leq l_1 \leq l \leq l_2 \leq N$ și $1 \leq c_1 \leq c \leq c_2\leq M$.

Cerință

Cum David nu a reușit până acum să combine zugrăvitul și programarea, vă roagă pe voi să îl ajutați să obțină punctajul maxim!

Date de intrare

Pe prima linie a fișierului de intrare trafalet.in se află două numere, $N$ și $M$.
Pe următoarele $N$ linii se află câte $M$ numere naturale, reprezentând elementele matricei $A$. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire trafalet.out conține punctajul maxim pe care îl poate obține David.

Restricții și precizări

• $1 \leq N, M \leq 500$.
• Valorile din celulele matricei $A$ sunt numere naturale mai mici decât $1 \ 000 \ 000 \ 000$.

Exemplul 1

trafalet.in

3 3 
1 2 1
3 5 2
1 2 4

trafalet.out

5

Explicație

În figura de mai jos submatricea selectată (indicată de un chenar albastru) este vopsită în alb.
Punctajul este $5 = 5 - 2 - 2 + 4$, și acest punctaj este maxim. Această soluție nu este unică.

Figura 1 din enunțul original al problemei Trafalet.Mărește schema ↗

Exemplul 2

trafalet.in

4 5
6 2 8 1 5
4 9 7 3 2
1 5 3 6 8
7 3 2 9 4

trafalet.out

19

Explicație

În figura de mai jos submatricea selectată (indicată de un chenar albastru) este vopsită în alb.
Punctajul este $19 = -2 + 8 - 1 + 5 + 9 - 7 + 3 - 2 - 5 + 3 - 6 + 8 + 3 - 2 + 9 - 4$, și acest punctaj este maxim.

Figura 2 din enunțul original al problemei Trafalet.Mărește schema ↗