P2331 [SCOI2005] Maximum Submatrix

There is an $n \times m$ matrix. Please choose $k$ submatrices so that the sum of their scores is maximized. Note: The chosen $k$ submatrices must be pairwise non-overlapping (no two share any cell).

The first line contains $n, m, k$. Each of the next $n$ lines contains $m$ integers, the scores of the elements in the matrix. The absolute value of each element’s score does not exceed $32767$.

Output a single line containing the maximum possible sum of the scores of the $k$ submatrices.

For $100\%$ of the testdata, $1 \leq n \leq 100$, $1 \leq m \leq 2$, $1 \leq k \leq 10$. Translated by ChatGPT 5