Nosaukums
Sulīgs perimetrs (sulper)
Laika limits
0.80s
Atmiņas limits
64.0 MB
Grūtība
43%

Definīcija

Normunds (Gudrinieku ciema iedzīvotājs) izlēma uzstādīt ābeles savā darzā. Viņa dārzs ir N × M laukums, katrā rūtiņā ir ierakstīts vesels skaitlis. Šis skaitlis apzīmē, cik sulīgi būs āboli kokam šajā rūtiņā (negatīvi skaitļi apzīmē sliktu augsni un negaršīgus ābolus).

Lai dārzs būtu arī skaisti sakopts, Normunds ir izlēmis uzstādīt ābeles uz kāda taisnstūra perimetra. Formāli, ja ir dots taisnstūris ar rindu numuriem no x1 līdz x2 (1 ≤ x1 < x2N), un ar kolonnu numuriem no y1 līdz y2 (1 ≤ y1 < y2M), tad Normunds uzstāda ābeles visās rūtiņās (xy), kur x1 ≤ x ≤ x2, y1 ≤ y ≤ y2 un vai nu x ir vienāds ar kādu no x1 vai x2, vai nu y ir vienāds ar kādu no y1 un y2. 

Normunds vēlas atrast tādu perimetru, lai maksimizētu kopējo ābolu sulīgumu tajā. Palīdziet viņam to izdarīt!

Piemēram, zemāk redzamā dārzā izvēlētajam perimetram kopējais sulīgums ir 5 – 5 + 4 – 8 – 8 + 1 – 2 + 3 + 5 + 9 – 2 + 2 + 5 + 4 = 13.


Ievaddatu raksturojums

Pirmajā rindā doti divi skaitļi N un M, rindu un kolonnu skaits (2 ≤ N, M ≤ 500). Tālāk dotas N rindas ar M skaitļiem katrā, kas apraksta dārzu, i-tajā rindā j-tajā pozīcijā ir dots rūtiņas (ij) sulīgums aij (–106 ≤ aij ≤ 106).


Izvaddatu raksturojums

Vienīgā rindā izvadiet maksimālo iespējamo kopējo ābeļu sulīgumu.


Piezīmes

Apakšuzdevuma apraksts Punktu skaits
N, M ≤ 100 20
Bez papildus ierobežojumiem 80

Kopā:   

100


Paraugdati

Stdin
6 8
9 -6 -1 2 -4 2 1 -7
1 5 -5 4 -8 -8 5 2
-5 4 -3 9 -3 1 2 -4
-1 5 6 -2 6 -2 -5 7
4 2 -2 9 5 3 2 7
9 -7 8 8 -4 -9 -1 -2
Stdout
44

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.