Land Inheritance

Time limit10sMemory limit512 MB

Summary

Given an H by W grid of prices, split it into N non-overlapping rectangles so that the smallest rectangle sum is as large as possible, and report that sum.

Level: Medium7 of 10
Topics: Binary search, Dynamic programming, Prefix sum, Matrix
Solved: No attempts yet

Problem

A family of $N$ brothers is dividing the vast land left by their parents. The land is a rectangle $H$ km from north to south and $W$ km from west to east. It is managed in 1 km square cells. The cell that lies from $i$ to $i+1$ km from the north edge and from $j$ to $j+1$ km from the west edge is called cell $(i, j)$ , where $i$ and $j$ are integers with $0 \leq i < H$ and $0 \leq j < W$ . Each cell has a price, and the price of cell $(i, j)$ is $a_{i,j}$ .

The brothers divide the land as follows.

Each brother chooses some cells and inherits them.
The cells each brother inherits must form one rectangle.
The land inherited by the $N$ brothers must not overlap.
Some cells may go to nobody. Those cells are abandoned.

The price of a brother's land is the sum of the prices of the cells in that brother's rectangle. The brothers want the prices to be as fair as possible. Find the division that maximizes the lowest land price among the $N$ brothers, and print that lowest price.

Input

The input is given in the following format.

H W N
a_{0,0} a_{0,1} ... a_{0,W-1}
...
a_{H-1,0} a_{H-1,1} ... a_{H-1,W-1}

$H$ and $W$ ( $2 \leq H, W \leq 200$ ) are the north-south and east-west lengths of the land. $N$ ( $2 \leq N \leq 4$ ) is the number of brothers. $a_{i,j}$ ( $0 \leq a_{i,j} \leq 10^4$ ) is the price of cell $(i, j)$ .

Output

Print the lowest land price on one line when the land is divided to maximize that price.

Examples5

Example 1
Input
```
3 3 2
1 2 2
3 1 0
0 4 3
```
Expected output
```
7
```
Example 2
Input
```
3 3 2
0 1 0
1 1 1
0 1 0
```
Expected output
```
1
```
Example 3
Input
```
2 5 3
8 3 0 5 6
2 5 2 5 2
```
Expected output
```
11
```
Example 4
Input
```
3 3 4
3 3 4
3 3 4
3 3 4
```
Expected output
```
7
```

Example 5

Input

Expected output