Maximum Sum of K Non-Overlapping Submatrices

You are given an $N \times M$ matrix of integers. Choose exactly $K$ pairwise non-overlapping submatrices so that the total sum of all elements contained in the chosen submatrices is as large as possible.

A submatrix is a rectangular block cut from the matrix, formed by consecutive rows and consecutive columns, and its size is at least $1 \times 1$. Two submatrices overlap if they share at least one common cell. Touching only along an edge or at a corner does not count as overlapping.

The first line contains three space-separated integers $N$, $M$, and $K$: the number of rows, the number of columns, and the number of submatrices you must choose. ($1 \le K \le 3$, $K \le N \le 300$, $K \le M \le 300$)

Each of the next $N$ lines contains $M$ space-separated integers. The $j$-th integer on the $i$-th line is the element $a_{ij}$ at row $i$ and column $j$. ($-20000 \le a_{ij} \le 20000$)

Print, on a single line, the maximum possible sum of all elements contained in the $K$ chosen submatrices.

You must choose exactly $K$ submatrices, and each submatrix is at least $1 \times 1$. Even when every element is negative you still have to choose $K$ of them, so pick them to minimize the loss.