Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Sumakampis

Maskvos oro uostas, 2019. Vytautas kalbasi su savim.

Vytautas 1: Kaip pavadint uždavinį, kur skaičių matricoje reikia rasti stačiakampį su didžiausia suma?

Vytautas 2: "Maksimalus stačiakampis"?

Vytautas 1: Nuobodu taip, reik kažko įdomesnio.

Vytautas 2: Tai tada kokį nors "submatricėlė", kad smagiau būtų.

Vytautas 1: Ne, nesąmonė.

Vytautas 3: Žinau! "Sumakampis"! Pagauni? Stačiakampis + suma = sumakampis!

Vytautas 1: Iš kur tu atsirad...

Vytautas 2: Jo jo, šitas geras!

Vytautas 1: *atsidūsta* Gerai...

Iš pateiktos monologo ištraukos uždavinio sąlyga jau turbūt aiški. Tačiau, dėl visa ko, štai formalus apibrėžimas. Jums duota lentelė, kurios kiekviename langelyje įrašyta po kažkokį sveikąjį skaičių. Lentelė turi n eilučių ir m stulpelių. Jūsų užduotis - šioje lentelėje rasti vientisą stačiakampį, kurio suma būtų maksimali.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir m - lentelės eilučių ir stulpelių kiekiai (1\\leqn,m\\leq256).

Toliau seka n eilučių po m sveikųjų skaičių, aprašančių pačią lentelę. Visi skaičiai yra intervale [-10^9,10^9].

Rezultatai

Jūsų programa turi išvesti vienintelį sveikąjį skaičių - didžiausią įmanomą vientiso stačiakampio, sudaryto iš lentelės skaičių, sumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
 
15