English
Zadanie Zamieć (zam)
Zamieć
Limit pamięci: 128 MB
Nad Bajtołami Dolnymi przeszła zamieć. Ulice zostały pokryte wieloma metrami śniegu, a prognoza na najbliższe dni zapowiada mróz. Wszystko wskazuje na to, że jeszcze przez wiele dni mieszkańcy spędzą sporo czasu w swoich domach.
W tej sytuacji Bajtazar postanowił zająć się rozwiązywaniem następującego problemu algorytmicznego, który znalazł w Głosie Bajtołów.
Dana jest macierz (tj. tabelka) liczb całkowitych.
Należy znaleźć takie 
nienachodzących na siebie prostokątnych podtablic tej macierzy, że suma liczb w tych podtablicach jest jak największa.
Każda z podtablic musi zawierać co najmniej jedną komórkę.
Napisz program, który rozwiąże problem, z którym walczy Bajtazar.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite 
, 
i 
(
, 
) oznaczające odpowiednio wysokość i szerokość macierzy oraz liczbę poszukiwanych podtablic.
Kolejne 
wierszy opisuje poszczególne wiersze danej tablicy.
Każdy z nich składa się z ciągu 
liczb całkowitych 
(
).
Dodatkowo, w testach wartych łącznie 
punktów, 
.
Wyjście
Wypisz jedną liczbę całkowitą równą największej możliwej sumie liczb w
podtablicach podanej tablicy.
Brzegi wybranych podtablic mogą się dotykać, jednak same podtablice nie mogą mieć wspólnych komórek.
Przykład
Dla danych wejściowych:
4 5 2 6 -10 0 3 -6 -8 8 1 -5 3 -7 -3 2 4 -4 2 0 -1 3 -3
poprawną odpowiedzią jest:
17
Zadanie zapożyczone z CPSPC 2010.