You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小项和朋友们一共 $k$ 个人，刚刚购买了一个长度为 $m$，宽度为 $n$ 的矩形蛋糕，准备大伙一起分着吃，不过这个蛋糕上面的草莓不是很均匀。如果我们把这个矩形蛋糕划分成 $n×m$ 的网格，可以观察得第 $i$ 行第 $j$ 列的网格上有 $a_{i,j}$ 颗草莓。

大家都因为草莓分配的事情争论不休，每个人都想获得更多的草莓，于是，聪明的小项想出了一个好办法，就由他自己来负责切蛋糕，不过他只能拿到最后一块蛋糕（最后一块蛋糕草莓最少）。

特别需要说明的是，小项每次只能从一块蛋糕的边缘，沿着每个网格的边缘线横切或者竖切蛋糕直到蛋糕的另外一个边缘，并且不能改变刀的移动方向从而把一块蛋糕分成两块，求出小项把整个蛋糕分成 $k$ 块的所有方案中，他能获得最多草莓的数量。

输入格式

从文件 cake.in 中读入数据。 第一行包含三个数字 $n,m,k$，分别表示蛋糕的长度、蛋糕的宽度、及蛋糕分成的块数。 接下来 $n$ 行，每行 $m$ 个数字，每个数字 $a_{i,j}$ 表示每个网格上的草莓数量。

输出格式

输出到文件 cake.out。 输出仅一个数字，表示小项能够获得的最大草莓数。

样例

3 3 4
4 4 2
2 9 6
6 5 3

9

样例解释

如下图切割蛋糕的方案最优（加粗黑线为切割处），4 块蛋糕的草莓数分别是 10、11、11、9。小项是最后一个取蛋糕的人，只能分得最少的草莓 9。

下图也是一种分蛋糕的方案，但是小项只能获得最小的那块，只能获得 8 颗草莓。

数据范围

对于所有测试数据有： $1\le n,m\le 30$， $0< k\le n×m$， $0\le a_{i,j}\le 100$。