Maximum Sum of k Non-Overlapping Submatrices

You are given an \( n \times m \) matrix \( A \) with integer elements. Your task is to choose exactly \( k \) submatrices (rectangular contiguous areas) such that the sum of their elements is maximized. The submatrix defined by its top-left corner \( (r_1, c_1) \) and bottom-right corner \( (r_2, c_2) \) has a sum computed as

[ S = \sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{ij} ]

Two submatrices are considered non-overlapping if they do not share any common cell. In other words, two submatrices \( (r_1^1, c_1^1, r_2^1, c_2^1) \) and \( (r_1^2, c_1^2, r_2^2, c_2^2) \) are non-overlapping if at least one of the following conditions holds:

[ \begin{cases} r_2^1 < r_1^2, \quad \text{or}\ r_1^1 > r_2^2, \quad \text{or}\ c_2^1 < c_1^2, \quad \text{or}\ c_1^1 > c_2^2. \end{cases} ]

Your goal is to select exactly \( k \) non-overlapping submatrices so that the total sum of all chosen submatrices is maximized.

Note: The input constraints are such that \( n \) and \( m \) are small (for example, \( n, m \le 5 \)) so that a brute force or backtracking approach is feasible.

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \) (where \( 1 \le n, m \le 5 \)). Each of the following \( n \) lines contains \( m \) integers, representing the matrix \( A \).

For example:

3 3 2
-1 2 3
4 -5 6
7 8 -9

outputFormat

Output a single integer, the maximum total sum achievable by selecting exactly \( k \) non-overlapping submatrices.

sample

2 2 1
1 2
3 4

10