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

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.