Żarłoczni Fizycy

Autor: Karol Kurach, program wzorcowy: Kamil Anikiej

Michał i Radek to koledzy ze szkoły. Obaj bardzo interesują się fizyką i odnoszą sukcesy w Olimpiadzie Fizycznej. Z okazji ostatnich wygranych zawodów, pani Elżbieta nagrodziła ich ogromnym, własnoręcznie wykonanym tortem.

Tort ma kształt prostokąta o wymiarach n x m i składa się z n * m kwadratowych segmentów. Koledzy mają zamiar podzielić go na 2 części. Niestety, tort nie jest taki sam w każdym miejscu. Każdemu segmentowi S(n,m) przypisana jest pewna liczba całkowita określająca jego smakowitość. Fizycy od razu odrzucili .prostacką. wg nich metodę podziału toru na pół i wylosowania kto dostanie lepszy kawałek. Zamiast tego postanowili zagrać w swojego rodzaju grę i podzielić tort zachowując przy tym poniższe reguły:

Grę zaczyna Radek, do niego należą segmenty na lewo od linii cięcia, do Michała na prawo od linii cięcia. Wygrywa oczywiście ten, u którego suma smakowitości wszystkich segmentów jest większa.

Jak to w życiu bywa , nie wszystkie strony pojedynku przestrzegają zasad fair-play. Michał, wieloletni prenumerator .Wróżki. potrafi przewidywać wyniki swych posunięć i zawsze gra perfekcyjnie. Wyrównaj szanse ! Pomóż Radkowi zjeść najbardziej smakowity kąsek zakładając , że jego przeciwnik gra bezbłędnie.

Zadanie

Napisz program, który:

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite n, m , 1 <= n , m <= 2000 oddzielone pojedynczym odstępem. Liczba n oznacza szerokość tortu, m . jego długość.

Kolejne n wierszy zawiera po m liczb całkowitych z przedziału <- 100000, 100000 > pooddzielanych pojedynczymi odstępami ; j-ta liczba w (i+1)-szym wierszu oznacza smakowitość segmentu (n- i+1 , j ) . [ (1,1)- lewy dolny segment ; (n,m) . prawy górny segment ] W kartezjańskim układzie współrzędnych, segment (1,1) oznacza po prostu kwadrat otoczony punktami (0,0), (0,1), (1,0), (1,1) , a segment (n,m) kwadrat otoczony punktami (m-1,n-1), (m-1,n) , (m,n-1) , (m,n).

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znajdować się liczba całkowita określająca największą smakowitość, jaką Radek może uzyskać dla swojej części tortu.

Przykład

Dla danych wejściowych:

3 4
1 1 1 1
1 2 1 1
1 1 1 1

Poprawnym wynikiem jest:

7

Komentarz:

Podział tortu wygląda następująco ( segmenty R . własność Radka , M . Michała )

RRRM
RRMM
RMMM

( w tym wypadku Radek kroił cały czas w prawo a Michał w górę, czerwone .R. oznacza segment (1,1) )

UWAGI:

Limit pamięci : 8 MB