Gudrinieku ciemā ir paslēpts daudz dārgumu. Pats ciems ir N × M režģis, katrā rūtiņā ir apslēpti dārgumi.

Atklājās, ka dārgumi var būt vai nu no zelta, vai nu antizelta. Zelta dārgumiem ir pozitīva vērtība, antizelta – negatīva vērtība. Dārgumi ir paslēpti katrā no rūtiņām.

Dārgumus var izrakt šādā veidā: var izvēlēties divus rindiņas numurus i₁, i₂ (i₁ ≤ i₂), divus kolonnu numurus j₁, j₂ (j₁ ≤ j₂), un izrakt visus dārgumus, kas atrodas rūtiņas (x, y) tādās, ka tieši viens no nosacījumiem izpildās:

• i₁ ≤ x ≤ i₂;
• _j1 ≤ y ≤ j₂.

Kopējā iegūtā vērtība ir visu izrakto dārgumu vērtību summa. Piemēram, ja N = 6, M = 8, i₁ = 2, i₂ = 4, j₁ = 3, j₂ = 7, tad summā jāieskaita skaitļi iekrāsotajās rūtiņās:

Kāda ir lielākā iespējamā kopējā vērtība, ja izvēlēties numurus i₁, i₂, j₁, j₂ optimāli?

Pirmajā rindā doti divi naturāli skaitļi N un M (1 ≤ N, M ≤ 500), ciema izmēri.

Nākamajās M rindas katrā dots pa N veseliem skaitļiem, dārgumu vērtības. Visi skaitļi pēc absolūtās vērtības nepārsniedz 1000.

Izvadiet vienu veselu skaitli, lielāko iespējamo summu, ko var iegūt.