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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e14+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-12;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

llint wa[201][201]={0};
llint erea(int L,int R,int U,int D){return wa[U][L]+wa[D][R]-wa[U][R]-wa[D][L];}
bool solve(int L,int R,int U,int D,int n,llint ter){
	if(erea(L,R,U,D)<ter*n){return false;}//明らかに足りない
	if(n==1){return true;}
	//左埋めパターン
	int bas;
	bas=L;
	while(erea(L,bas,U,D)<ter){bas++;}
	if(solve(bas,R,U,D,n-1,ter)){return true;}
	bas=R;
	while(erea(bas,R,U,D)<ter){bas--;}
	if(solve(L,bas,U,D,n-1,ter)){return true;}
	bas=U;
	while(erea(L,R,U,bas)<ter){bas++;}
	if(solve(L,R,bas,D,n-1,ter)){return true;}
	bas=D;
	while(erea(L,R,bas,D)<ter){bas--;}
	if(solve(L,R,U,bas,n-1,ter)){return true;}
	if(n==4){
		for(int M=U+1;M<=D-1;M++){
			if(erea(L,R,U,M)<ter){continue;}
			if(erea(L,R,M,D)<ter){continue;}
			int ux=L+1;
			while(erea(L,ux,U,M)<ter){ux++;}
			int dx=L+1;
			while(erea(L,dx,M,D)<ter){dx++;}
			if(ux<dx){
				int sy=D-1;
				while(sy>=U&&erea(dx,R,sy,D)<ter){sy--;}
				if(sy<U){continue;}
				if(M<sy){
					if(erea(ux,R,U,M)>=ter){return true;}
					if(erea(dx,R,U,sy)>=ter){return true;}
				}else{
					if(erea(ux,R,U,sy)>=ter){return true;}
				}
			}else{
				int sy=U+1;
				while(sy<=D&&erea(ux,R,U,sy)<ter){sy++;}
				if(sy>D){continue;}
				if(M>sy){
					if(erea(dx,R,M,D)>=ter){return true;}
					if(erea(ux,R,sy,D)>=ter){return true;}
				}else{
					if(erea(dx,R,sy,D)>=ter){return true;}
				}
			}
		}
	}
	return false;
}
int main(void){
	cout<<fixed<<setprecision(20);
	cin.tie(0);ios::sync_with_stdio(false);
	int h,w,i,j,n;cin>>h>>w>>n;
	
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){cin>>wa[i][j];wa[i][j]+=wa[i][j-1];}
	}
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){wa[i][j]+=wa[i-1][j];}
	}
	llint bmin=0,bmax=wa[h][w]/n+1;
	while(bmax-bmin>1){
		llint bgen=(bmax+bmin)/2;
		if(solve(0,w,0,h,n,bgen)){bmin=bgen;}
		else{bmax=bgen;}
		
	}
	cout<<bmin<<endl;return 0;
	return 0;
}