7276 - 分蛋糕（cake）
时间限制 : 1 秒
内存限制 : 512 MB
小项和朋友们一共k个人，刚刚购买了一个长度为m，宽度为n的矩形蛋糕，准备大伙一起分着吃，不过这个蛋糕上面的草莓不是很均匀。如果我们把这个矩形蛋糕划分成n×m的网格，可以观察得第i行第j列的网格上有a_(i,j)颗草莓。
大家都因为草莓分配的事情争论不休，每个人都想获得更多的草莓，于是，聪明的小项想出了一个好办法，就由他自己来负责切蛋糕，不过他只能拿到最后一块蛋糕（最后一块蛋糕草莓最少）。
特别需要说明的是，小项每次只能从一块蛋糕的边缘，沿着每个网格的边缘线横切或者竖切蛋糕直到蛋糕的另外一个边缘，并且不能改变刀的移动方向从而把一块蛋糕分成两块，求出小项把整个蛋糕分成k块的所有方案中，他能获得最多草莓的数量。
输入
第一行包含三个数字n,m,k，分别表示蛋糕的长度、蛋糕的宽度、及蛋糕分成的块数。
接下来n行，每行m个数字，每个数字a_(i,j)表示每个网格上的草莓数量。
输出
输出仅一个数字，表示小项能够获得的最大草莓数。
样例
输入
3 3 4 4 4 2 2 9 6 6 5 3
输出
9
输入
3 4 7 4 5 6 4 1 5 7 1 3 4 4 3
输出
5
输入
10 10 22 9 8 3 6 9 2 4 9 4 1 7 9 2 4 1 7 1 5 4 7 10 8 7 8 9 10 4 9 8 9 2 1 8 3 4 5 10 5 9 2 5 1 2 9 4 2 3 5 4 3 8 4 5 9 6 5 6 9 2 8 1 4 3 7 8 9 2 6 5 2 10 9 3 10 9 1 5 5 3 4 5 2 2 5 6 1 7 2 3 9 4 5 5 8 3 2 1 8 4 2
输出
21
提示
【样例1解释】
如下图切割蛋糕的方案最优（加粗黑线为切割处），4块蛋糕的草莓数分别是10、11、11、9。小项是最后一个取蛋糕的人，只能分得最少的草莓9。
下图也是一种分蛋糕的方案，但是小项只能获得最小的那块，只能获得8颗草莓。
【数据范围】
对于所有测试数据有：1≤ n,m≤30，0< k≤n×m,0≤a_(i,j)≤100
来源
云南精英赛