Problem: 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.

<image>


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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using vi = std::vector<int64_t>;
using vvi = std::vector<vi>;

int H, W, N;
vvi values;

int topFind(int, int, int, int, int64_t);
int bottomFind(int, int, int, int, int64_t);
int leftFind(int, int, int, int, int64_t);
int rightFind(int, int, int, int, int64_t);
bool condition(int, int, int, int, int, int64_t);
int64_t calcArea(int, int, int, int);

int main()
{
	scanf("%d%d%d", &H, &W, &N);
	values.resize(H + 1, vi(W + 1));
	for (int i{1}; i <= H; i++)
		for (int j{1}; j <= W; j++)
			scanf("%lld", &values[i][j]);
	for (int i{1}; i <= H; i++)
		for (int j{1}; j <= W; j++)
			values[i][j] += values[i][j - 1];
	for (int i{1}; i <= W; i++)
		for (int j{1}; j<= H; j++)
			values[j][i] += values[j - 1][i];
	int64_t ng{1ll << 60}, ok{};
	while (ng - ok > 1)
	{
		int64_t mid{(ok + ng) >> 1};
		if (condition(0, 0, H, W, N, mid)) ok = mid;
		else ng = mid;
	}
	printf("%lld\n", ok);
	
	return 0;
}

bool condition(int top, int left, int bottom, int right, int N, int64_t lowbou)
{
	if (N == 0) return true;
	if (calcArea(top, left, bottom, right) < N * lowbou) return false;
	int midtop{topFind(top, left, bottom, right, lowbou)}, midleft{leftFind(top, left, bottom, right, lowbou)};
	int midbottom{bottomFind(top, left, bottom, right, lowbou)}, midright{rightFind(top, left, bottom, right, lowbou)};
	if (condition(midtop, left, bottom, right, N - 1, lowbou) || condition(top, midleft, bottom, right, N - 1, lowbou)
		|| condition(top, left, midbottom, right, N - 1, lowbou) || condition(top, left, bottom, midright, N - 1, lowbou)
		)
		return true;
	if (N <= 3) return false;
	for (int h_i{1}; h_i <= H; h_i++)
	{
		if (calcArea(0, 0, h_i, W) < lowbou) continue;
		int r{rightFind(0, 0, h_i, W, lowbou)};
		if (calcArea(0, 0, H, r) < lowbou) continue;
		int t{std::max(h_i, topFind(0, 0, H, r, lowbou))};
		if (calcArea(t, 0, H, W) < lowbou) continue;
		int l{std::max(r, leftFind(t, 0, H, W, lowbou))};

		if (calcArea(h_i, l, H, W) >= lowbou) return true;
	}
	for (int h_i{1}; h_i <= H; h_i++)
	{
		if (calcArea(0, 0, h_i, W) < lowbou) continue;
		int l{leftFind(0, 0, h_i, W, lowbou)};
		if (calcArea(0, l, H, W) < lowbou) continue;
		int t{std::max(h_i, topFind(0, l, H, W, lowbou))};
		if (calcArea(t, 0, H, W) < lowbou) continue;
		int r{std::min(l, rightFind(t, 0, H, W, lowbou))};

		if (calcArea(h_i, 0, H, r) >= lowbou) return true;
	}
	return false;
}

int topFind(int top, int left, int bottom, int right, int64_t lowbou)
{
	int ng{top - 1}, ok{bottom};
	while (ok - ng > 1)
	{
		int mid{(ok + ng) >> 1};
		if (calcArea(top, left, mid, right) >= lowbou)
			ok = mid;
		else
			ng = mid;
	}
	return ok;
}

int leftFind(int top, int left, int bottom, int right, int64_t lowbou)
{
	int ng{left - 1}, ok{right};
	while (ok - ng > 1)
	{
		int mid{(ok + ng) >> 1};
		if (calcArea(top, left, bottom, mid) >= lowbou)
			ok = mid;
		else
			ng = mid;
	}
	return ok;
}

int bottomFind(int top, int left, int bottom, int right, int64_t lowbou)
{
	int ok{top}, ng{bottom + 1};
	while (ng - ok > 1)
	{
		int mid{(ok + ng) >> 1};
		if (calcArea(mid, left, bottom, right) >= lowbou)
			ok = mid;
		else
			ng = mid;
	}
	return ok;
}

int rightFind(int top, int left, int bottom, int right, int64_t lowbou)
{
	int ok{left}, ng{right + 1};
	while (ng - ok > 1)
	{
		int mid{(ok + ng) >> 1};
		if (calcArea(top, mid, bottom, right) >= lowbou)
			ok = mid;
		else
			ng = mid;
	}
	return ok;
}

int64_t calcArea(int top, int left, int bottom, int right)
{
	return values[bottom][right] + values[top][left] - values[bottom][left] - values[top][right];
}