Land Inheritance

F --Land inheritance

Problem Statement

One $N$ brother was discussing the inheritance of his parents. The vast heritage left by their parents included vast lands. The land has a rectangular shape extending $H$ km from north to south and $W$ km from east to west. This land is managed in units of 1 km square, 1 km square within the range of $i$ to $i + 1$ km from the north end of the land and $j$ to $j + 1$ km from the west end. The partition is called partition $(i, j)$. ($i$, $j$ is an integer that satisfies $0 \ leq i <H$, $0 \ leq j <W$.) The land price is fixed for each lot, and the lot $(i, j)$ The price of is represented by $a_ {i, j}$.

The brothers decided to divide the land and inherit it as follows.

• $N$ Each of the siblings chooses some parcels and inherits them.
• The parcels must be chosen so that the land inherited by each sibling forms a rectangle.
• $N$ Lands inherited by brothers must not overlap.
• There may be compartments where no one inherits. The parcels that no one inherits are abandoned.

The sum of the prices of the lots included in the range of land inherited by a person is called the price of the land. The brothers want to divide the land so that the price of the land they inherit is as fair as possible. Your job is to think of ways to divide the land that maximizes the price of the land of the person with the lowest inherited land price among the $N$ people. Create a program that answers the land price of the person with the lowest inherited land price when the land is divided in this way.

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$, $W$$(2 \ leq H, W \ leq 200)$ represent the north-south length and the east-west length of the heritage land, respectively. $N$$(2 \ leq N \ leq 4)$ represents the number of siblings who inherit the land. $a_ {i, j}$$(0 \ leq a_ {i, j} \ leq 10 ^ 4)$ represents the price of the partition $(i, j)$.

Output

Output the lowest land price in one line when the land price of the person with the lowest inherited land price is divided so as to maximize the land price.

Sample Input 1

3 3 2 1 2 2 3 1 0 0 4 3

Output for the Sample Input 1

7

It is best to divide as shown in the figure.

Sample Input 2

3 3 2 0 1 0 1 1 1 0 1 0

Output for the Sample Input 2

1

Sample Input 3

2 5 3 8 3 0 5 6 2 5 2 5 2

Output for the Sample Input 3

11

Sample Input 4

3 3 4 3 3 4 3 3 4 3 3 4

Output for the Sample Input 4

7

Sample Input 5

4 4 4 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 1

Output for the Sample Input 5

7

Example

Input

3 3 2 1 2 2 3 1 0 0 4 3

Output

7

inputFormat

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$, $W$$(2 \ leq H, W \ leq 200)$ represent the north-south length and the east-west length of the heritage land, respectively. $N$$(2 \ leq N \ leq 4)$ represents the number of siblings who inherit the land. $a_ {i, j}$$(0 \ leq a_ {i, j} \ leq 10 ^ 4)$ represents the price of the partition $(i, j)$.

outputFormat

Output

Output the lowest land price in one line when the land price of the person with the lowest inherited land price is divided so as to maximize the land price.

Sample Input 1

3 3 2 1 2 2 3 1 0 0 4 3

Output for the Sample Input 1

7

It is best to divide as shown in the figure.

Sample Input 2

3 3 2 0 1 0 1 1 1 0 1 0

Output for the Sample Input 2

1

Sample Input 3

2 5 3 8 3 0 5 6 2 5 2 5 2

Output for the Sample Input 3

11

Sample Input 4

3 3 4 3 3 4 3 3 4 3 3 4

Output for the Sample Input 4

7

Sample Input 5

4 4 4 2 2 2 2 2 1 2 1 2 2 2 2 2 1 2 1

Output for the Sample Input 5

7

Example

Input

3 3 2 1 2 2 3 1 0 0 4 3

Output

7

样例

3 3 2
1 2 2
3 1 0
0 4 3

7