Maximum Sum of K Non-Overlapping Submatrices

Time limit2sMemory limit32 MB

Summary

Pick exactly K pairwise non-overlapping rectangular submatrices from an N x M matrix to maximize the sum of their elements.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum, Implementation, Brute force
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Hint

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.

Examples6

Example 1

Input

4 5 2
6 -10 0 3 -6
-8 8 1 -5 3
-7 -3 2 4 -4
2 0 -1 3 -3

Expected output

Example 2
Input
```
3 4 1
1 2 -1 0
-3 4 5 -2
0 1 2 3
```
Expected output
```
14
```
Example 3
Input
```
2 2 1
-5 -2
-9 -3
```
Expected output
```
-2
```
Example 4
Input
```
3 3 3
1 2 3
4 5 6
7 8 9
```
Expected output
```
45
```
Example 5
Input
```
3 3 2
-1 -2 -3
-4 -5 -6
-7 -8 -9
```
Expected output
```
-3
```
Example 6
Input
```
2 3 1
1 2 3
4 5 6
```
Expected output
```
21
```