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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(kbrni,n)cout<<" "<<a[kbrni];cout<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define svecp(v) cout<<#v<<":";each(kbrni,v)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 205;

int h,w,n;

int a[MAX_N][MAX_N];
int tmp[MAX_N][MAX_N];
int sm[MAX_N][MAX_N];

int cal(int ul,int dr,int dl,int ur)
{
    return sm[dl+1][ur+1]-sm[dl+1][dr]-sm[ul][ur+1]+sm[ul][dr];
}

void rot(int h,int w)
{
    rep(i,h){
        rep(j,w){
            tmp[i][j] = a[i][j];
        }
    }
    rep(i,w){
        rep(j,h){
            a[i][j] = tmp[j][w-1-i];
        }
    }
}

void sym(int h,int w){
    rep(i,h){
        rep(j,w){
            tmp[i][j] = a[i][j];
        }
    }
    rep(i,h){
        rep(j,w){
            a[i][j] = tmp[i][w-1-j];
        }
    }
}

void calcsum(int h,int w)
{
    rep(i,h+1){
        rep(j,w+1){
            sm[i][j] = 0;
        }
    }
    rep(i,h){
        rep(j,w){
            sm[i+1][j+1] = sm[i+1][j] + a[i][j];
        }
    }
    rep(j,w+1){
        rep(i,h){
            sm[i+1][j] += sm[i][j];
        }
    }
}

int solve(int h,int w,int n,int kind)
{
    calcsum(h,w);
    int mx = -1;
    if(n == 4){
        rep(i,w-1){
            rep(j,h-1){
                rep(k,h-1){
                    cmx(mx,min({cal(0,0,j,i),cal(j+1,0,h-1,i),cal(0,i+1,k,w-1),cal(k+1,i+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            srep(j,i+1,w-1){
                rep(k,h-1){
                    cmx(mx,min({cal(0,0,h-1,i),cal(0,i+1,k,j),cal(k+1,i+1,h-1,j),cal(0,j+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-1){
            rep(j,h-2){
                srep(k,j+1,h-1){
                    cmx(mx,min({cal(0,0,j,i),cal(j+1,0,k,i),cal(k+1,0,h-1,i),cal(0,i+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            srep(j,i+1,w-1){
                rep(k,h-1){
                    cmx(mx,min({cal(0,0,k,i),cal(k+1,0,h-1,i),cal(0,i+1,h-1,j),cal(0,j+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            rep(j,h-1){
                srep(k,i+1,w-1){
                    cmx(mx,min({cal(0,0,j,k),cal(j+1,0,h-1,i),cal(j+1,i+1,h-1,k),cal(0,k+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            rep(j,h-1){
                srep(k,i+1,w-1){
                    cmx(mx,min({cal(0,0,j,i),cal(0,i+1,j,k),cal(j+1,0,h-1,k),cal(0,k+1,h-1,w-1)}));
                }
            }
        }
        if(kind == 0){
            rep(i,w-2){
                srep(j,i+1,w-1){
                    rep(k,h-2){
                        srep(l,k+1,h-1){
                            cmx(mx,min({cal(0,0,l,i),cal(l+1,0,h-1,j),cal(0,i+1,k,w-1),cal(k+1,j+1,h-1,w-1)}));
                        }
                    }
                }
            }
        }
        sym(h,w);
        calcsum(h,w);
        rep(i,w-1){
            rep(j,h-2){
                srep(k,j+1,h-1){
                    cmx(mx,min({cal(0,0,j,i),cal(j+1,0,k,i),cal(k+1,0,h-1,i),cal(0,i+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            srep(j,i+1,w-1){
                rep(k,h-1){
                    cmx(mx,min({cal(0,0,k,i),cal(k+1,0,h-1,i),cal(0,i+1,h-1,j),cal(0,j+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-3){
            srep(j,i+1,w-2){
                srep(k,j+1,w-1){
                    cmx(mx,min({cal(0,0,h-1,i),cal(0,i+1,h-1,j),cal(0,j+1,h-1,k),cal(0,k+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            rep(j,h-1){
                srep(k,i+1,w-1){
                    cmx(mx,min({cal(0,0,j,k),cal(j+1,0,h-1,i),cal(j+1,i+1,h-1,k),cal(0,k+1,h-1,w-1)}));
                }
            }
        }
        rep(i,w-2){
            rep(j,h-1){
                srep(k,i+1,w-1){
                    cmx(mx,min({cal(0,0,j,i),cal(0,i+1,j,k),cal(j+1,0,h-1,k),cal(0,k+1,h-1,w-1)}));
                }
            }
        }
        if(kind == 0){
            rep(i,w-2){
                srep(j,i+1,w-1){
                    rep(k,h-2){
                        srep(l,k+1,h-1){
                            cmx(mx,min({cal(0,0,l,i),cal(l+1,0,h-1,j),cal(0,i+1,k,w-1),cal(k+1,j+1,h-1,w-1)}));
                        }
                    }
                }
            }
        }
    }else if(n == 3){
        rep(i,w-1){
            rep(j,h-1){
                cmx(mx,min({cal(0,0,j,i),cal(j+1,0,h-1,i),cal(0,i+1,h-1,w-1)}));
            }
        }
        sym(h,w);
        calcsum(h,w);
        rep(i,w-1){
            rep(j,h-1){
                cmx(mx,min({cal(0,0,j,i),cal(j+1,0,h-1,i),cal(0,i+1,h-1,w-1)}));
            }
        }
        rep(i,w-2){
            srep(j,i+1,w-1){
                cmx(mx,min({cal(0,0,h-1,i),cal(0,i+1,h-1,j),cal(0,j+1,h-1,w-1)}));
            }
        }
    }else{
        rep(i,w-1){
            cmx(mx,min(cal(0,0,h-1,i),cal(0,i+1,h-1,w-1)));
        }
    }
    return mx;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> h >> w >> n;
    rep(i,h){
        rep(j,w){
            cin >> a[i][j];
        }
    }
    int r1 = solve(h,w,n,0);
    rot(h,w);
    swap(h,w);
    int r2 = solve(h,w,n,1);
    cout << max(r1,r2) << "\n";
    return 0;
}