Ещё больше веселья
Так прекрасно спать под открытым небом, просыпаться под пение птиц и видеть первые лучи солнца, встающего из-за горизонта...
Стоп, Вы же не помните, как уснули посреди леса. Единственное, что Вы помните, это что Вы покрывали что-то тремя прямоугольниками. 0_о
Будучи неуверенным в том, что же это было, Вы придумали себе следующую задачу: Для данной матрицы, состоящей из целых чисел, найти k неперекрывающихся подматриц (другими словами, прямоугольных фрагментов) таких, что сумма чисел в них была бы наибольшей.
Входные данные
В первой строке ввода находятся три целых числа n, m и k (1 ≤ k ≤ 3, k ≤ n, m ≤ 300), задающих количество строк, количество столбцов, и число подматриц соответственно. Следующие n чисел описывают матрицу построчно. Каждая из них содержит последовательность m целых чисел a_ij (-20000 ≤ a_ij ≤ 20000). Также известно, что в 40% тестов 1 ≤ k ≤ 2.
Выходные данные
Выведите одно целое число: наибольшую возможную сумму чисел в k подматрицах данной матрицы. Подматрицы могут касаться, но они не могут иметь общих элементов.
