Even more fun#5488
Sleeping under the open sky is so wonderful: waking to birdsong, seeing the first rays of the sun rising from behind the horizon...
But wait. You do not even remember how you fell asleep in the middle of the forest. The only thing you do recall is that you were covering something with three rectangles. 0_o
Not knowing exactly what this was, you come up with the following problem: Given an integer matrix, find non-overlapping submatrices (that is, rectangular fragments) such that the sum of their elements is maximized.
The first line contains three integers , , and (1 \le k \le 3, k \le n, m \le 300), representing the number of rows, columns, and submatrices, respectively. The following lines describe the matrix row by row, each containing integers a_{ij} (-20000 \le a_{ij} \le 20000). It is also given that in of the tests, 1 \le k \le 2.
Output a single integer: the maximum possible sum of the elements in submatrices of the given matrix. Submatrices may touch, but they must not share any elements.
Example 1