eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ещё больше веселья

Ещё больше веселья

Лимит времени 2 секунды
Лимит использования памяти 32 MiB

Так прекрасно спать под открытым небом, просыпаться под пение птиц и видеть первые лучи солнца, встающего из-за горизонта...

Стоп, Вы же не помните, как уснули посреди леса. Единственное, что Вы помните, это что Вы покрывали что-то тремя прямоугольниками. 0_о

Будучи неуверенным в том, что же это было, Вы придумали себе следующую задачу: Для данной матрицы, состоящей из целых чисел, найти k неперекрывающихся подматриц (другими словами, прямоугольных фрагментов) таких, что сумма чисел в них была бы наибольшей.

Входные данные

В первой строке ввода находятся три целых числа n, m и k (1k3, kn, m300), задающих количество строк, количество столбцов, и число подматриц соответственно. Следующие n чисел описывают матрицу построчно. Каждая из них содержит последовательность m целых чисел a_ij (-20000a_ij20000). Также известно, что в 40% тестов 1k2.

Выходные данные

Выведите одно целое число: наибольшую возможную сумму чисел в k подматрицах данной матрицы. Подматрицы могут касаться, но они не могут иметь общих элементов.

Пример

Входные данные #1
4 5 2
6 -10 0 3 -6
-8 8 1 -5 3
-7 -3 2 4 -4
2 0 -1 3 -3
Выходные данные #1
17