题目描述

joy家的玉米成熟啦。妈妈让Joy去采摘玉米，玉米植株整齐排列成一个矩形网格（图一）。joy已经知道每个玉米植株的玉米有多少。妈妈要求Joy：“先找出玉米最多的植株采摘玉米；然后找出剩下植株玉米最多的去采摘。依此类推，不过一定要在规定时间内回到路边。” Joy在单位时间内，可以做下列事情的一件： 1）从路边到第一行的某颗玉米植株； 2）采摘一颗玉米植株的玉米； 3）从一颗植株跳到相邻的另一个玉米植株；（仅能前后左右四个方向跳）； 4）从第一行的某颗玉米植株跳回路边；

现在给定一块玉米田的大小和玉米的分布，请问在限定时间内，Joy最多可以采到多少个玉米？注意可能只有部分植株下面长有玉米，假设这些植株下的玉米个数各不相同。 例如在图所示的玉米田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有玉米，个数分别为13, 7, 15, 9。沿着图示的路线，Joy在21个单位时间内，最多可以采到37个玉米。 【样例输入1】

6 7 21

0 0 0 0 0 0 0

0 0 0 0 13 0 0

0 0 0 0 0 0 7

0 15 0 0 0 0 0

0 0 0 9 0 0 0

0 0 0 0 0 0 0

【样例输出1】

37

输入格式

输入数据的第一行包括三个整数，M, N和K，用空格隔开；表示玉米田的大小为M * N（1 <= M, N <= 20），Joy采玉米的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示玉米田里植株(i, j)下玉米的数目，0表示该植株下没有玉米。

输出格式

输出包括一行，这一行只包含一个整数，即在限定时间内，Joy最多可以采到玉米的个数。

6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

37