Description

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).

Input Format

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 Format

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

3 2 2
1 -3
2 3
-2 3

9

Hint

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

Translated by ChatGPT 5