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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 205

int H,W,N;
ll table[NUM][NUM];

ll get_area(int row1,int col1,int row2,int col2){

	ll A,B,C,D;

	A = table[row2][col2];

	if(row1 == 0){
		B = 0;
	}else{
		B = table[row1-1][col2];
	}

	if(col1 == 0){
		C = 0;
	}else{
		C = table[row2][col1-1];
	}

	if(row1 == 0 || col1 == 0){
		D = 0;
	}else{
		D = table[row1-1][col1-1];
	}

	return A-(B+C)+D;
}

ll calc_2(int base_row,int base_col,int tmp_H,int tmp_W){ //★★左上のセル及び高さを指定する

	ll ret = 0;

	//左右に分割(0～mid列、mid+1～tmp_W-1列)
	for(int mid = 0; mid+1 <= tmp_W-1; mid++){
		ret = max(ret,min(get_area(base_row+0,base_col+0,base_row+tmp_H-1,base_col+mid),
				get_area(base_row+0,base_col+mid+1,base_row+tmp_H-1,base_col+tmp_W-1))); //最小値の最大値
	}

	//上下に分割(0～mid行、mid+1～tmp_H-1行)
	for(int mid = 0; mid+1 <= tmp_H-1; mid++){
		ret = max(ret,min(get_area(base_row+0,base_col+0,base_row+mid,base_col+tmp_W-1),
				get_area(base_row+mid+1,base_col+0,base_row+tmp_H-1,base_col+tmp_W-1)));
	}

	return ret;
}

ll calc_3(int base_row,int base_col,int tmp_H,int tmp_W){ //★★左上のセル及び高さを指定する

	ll ret = 0;

	/*★get_areaは座標指定、calc_2は基準及び高さ・幅指定なので注意★*/

	//まず上側に割る
	for(int mid = 0; mid+1 <= tmp_H-1; mid++){
		ret = max(ret,min(get_area(base_row+0,base_col+0,base_row+mid,base_col+tmp_W-1),
				calc_2(base_row+mid+1,base_col+0,tmp_H-1-mid,tmp_W)));
	}
	//まず下に割る
	for(int top = 1; top <= tmp_H-1; top++){
		ret = max(ret,min(calc_2(base_row+0,base_col+0,top,tmp_W),
				get_area(base_row+top,base_col+0,base_row+tmp_H-1,base_col+tmp_W-1)));
	}
	//まず左に割る
	for(int mid = 0; mid+1 <= tmp_W-1; mid++){
		ret = max(ret,min(get_area(base_row+0,base_col+0,base_row+tmp_H-1,base_col+mid),
				calc_2(base_row+0,base_col+mid+1,tmp_H,tmp_W-1-mid)));
	}
	//まず右に割る
	for(int left = 1; left <= tmp_W-1; left++){
		ret = max(ret,min(calc_2(base_row+0,base_col+0,tmp_H,left),
				get_area(base_row+0,base_col+left,base_row+tmp_H-1,base_col+tmp_W-1)));

	}

	return ret;
}

bool can_divide_4(int tmp_S){

	int H_1,H_2,W_3;
	int L,R,mid;
	//個々の面積をtmp_S以上に4分割できるか
	for(int right = 0; right <= W-2; right++){ //左上四角形の右端のループ

		//左上の高さを2分探索
		L = 1,R = H-1,mid = (L+R)/2;
		H_1 = -1;

		while(L <= R){

			if(get_area(0,0,mid-1,right) >= tmp_S){

				H_1 = mid;
				R = mid-1; //より高さを小さく

			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		if(H_1 == -1)continue;

		//右上の高さを2分探索
		L = 1,R = H-1,mid = (L+R)/2;
		H_2 = -1;

		while(L <= R){

			if(get_area(0,right+1,mid-1,W-1) >= tmp_S){

				H_2 = mid;
				R = mid-1; //より高さを小さく

			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		if(H_2 == -1)continue;

		//右下の幅を2分探索
		W_3 = -1;

		if(H_1 <= H_2){ //右下の幅を決定する際、左上との重なりを気にしなくて良い
			//★ただし、幅は右上以上でないといけない
			L = W-1-right, R = W-1, mid = (L+R)/2;

		}else{ //左上と重ならないように、右下の幅を決定する

			L = 1,R = W-1-right,mid = (L+R)/2;
		}

		while(L <= R){

			if(get_area(H_2,W-mid,H-1,W-1) >= tmp_S){

				W_3 = mid;
				R = mid-1;

			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}
		if(W_3 == -1)continue;

		//左下の面積
		if(get_area(H_1,0,H-1,W-W_3-1) >= tmp_S){
			return true;
		}
	}
	return false;
}

int calc_4(){

	ll ret = 0;

	/*★空白部なし★*/

	/*★get_areaは座標指定、calc_2は基準および高さ・幅指定なので注意★*/

	//まず上側に割る
	for(int mid = 0; mid+1 <= H-1; mid++){
		ret = max(ret,min(get_area(0,0,mid,W-1),calc_3(mid+1,0,H-1-mid,W)));
	}
	//まず下に割る
	for(int top = 1; top <= H-1; top++){
		ret = max(ret,min(calc_3(0,0,top,W),get_area(top,0,H-1,W-1)));
	}
	//まず左に割る
	for(int mid = 0; mid+1 <= W-1; mid++){
		ret = max(ret,min(get_area(0,0,H-1,mid),calc_3(0,mid+1,H,W-1-mid)));
	}
	//右に割る
	for(int left = 1; left <= W-1; left++){
		ret = max(ret,min(calc_3(0,0,H,left),get_area(0,left,H-1,W-1)));
	}

	//★ret以上の値を2分探索★
	ll left = ret,right = table[H-1][W-1]/4,mid = (left+right)/2;
	ll maximum = ret;

	while(left <= right){

		if(can_divide_4(mid)){

			maximum = mid;
			left = mid+1;

		}else{

			right = mid-1;
		}
		mid = (left+right)/2;
	}

	return maximum;
}

int main(){

	scanf("%d %d %d",&H,&W,&N);

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			scanf("%lld",&table[row][col]);
		}
	}

	/*★2次元累積和の処理★*/

	//左から右に足す
	for(int row = 0; row < H; row++){
		for(int col = 1; col < W; col++){
			table[row][col] += table[row][col-1];
		}
	}
	//上から下に足す
	for(int col = 0; col < W; col++){
		for(int row = 1; row < H; row++){
			table[row][col] += table[row-1][col];
		}
	}

	ll ans;

	switch(N){
	case 2:
		ans = calc_2(0,0,H,W);
		break;
	case 3:
		ans = calc_3(0,0,H,W);
		break;
	case 4:
		ans = calc_4();
		break;
	}

	printf("%lld\n",ans);

	return 0;
}