Rezolvare PBinfo #4606

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 (l1, c1) și colțul dreapta-jos (l2, c2) al submatricei. Submatricea conține elementele A[l][c] pentru 1 ≤ l1 ≤ l ≤ l2 ≤ N și 1 ≤ c1 ≤ c ≤ c2 ≤ M.

Cerința

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 ≤ N, M ≤ 500
• Valorile din celulele matricei A sunt numere naturale mai mici decât 1.000.000.000
• Pentru 40 de puncte, N, M ≤ 50
• Pentru 28 de puncte, N, M ≤ 150
• Pentru 32 de puncte, fără restricții suplimentare.

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

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.