HS-08 夏收记

你听见田垄底下那一声轻轻的拔节。 你嗅到新土、水汽和隔年的谷香。 你看见她弯下腰，把种子按进土里—— 像一个百年，和下一个百年。

题目背景

大荒城的夏天，是从田埂上第一株高粱抽穗那天开始的。

水渠里的水涨了又落，日头把土晒得发白，风一过，整片田就哗啦啦地响，像有人在很远的地方翻书。夏收前一夜，城里的人都去搭社戏的台子了，只有试验田边还亮着一盏灯。

题目描述

农业天师黍把她的学生禾生领到了田边。

这是禾生负责的“万顷”试验田：M 行 N 列，方方正正。田埂在北边，紧贴着第一行——从埂上任何一处跨进第一行的任何一株，都只算一步。育种失败的植株大多空着，只有少数几株底下结了花生，不多，但颗颗饱满。黍蹲下去，只看了一眼，就把每一株结了多少颗数了出来。她数过三遍，不会错；而且这些数目，两两不同。

明天是神农祭。小满说好了，要在社戏散场以后，用新收的花生给全城的孩子炒一锅。黍站起身，拍了拍手上的土：

“你去摘。不过，得按我的规矩来。”

其一，次序。

先摘结得最多的那一株，再摘剩下里最多的那一株，再摘次多的，如此往下，一株也不许跳。黍说，一篓种粮，要打最好的挑起——“种瓜得瓜，种豆得豆”，头一茬挑歪了，往后九代都跟着歪。

其二，工夫。

禾生每一个单位时间，只能做下面四件事中的一件：

1. 从田埂跳进第一行的某一株花生；
2. 从一株花生走到前后左右相邻的另一株；
3. 弯下腰，把一株花生摘下来；
4. 从第一行的某一株跳回田埂。

其三，香。

黍从袖子里摸出一截线香，递给站在埂上的左乐——小满管他叫“小烛台”，这差事倒正对口。香燃尽之前，禾生必须站回田埂上。同知荣晚晴批下来的条子上只写了一个数：这截香能烧 K 个单位时间，一寸也不多。

其四，不许回头。

下了田，脚就不能再沾田埂。大荒城的规矩——脚一沾埂，这一趟就算收了工，剩下的花生再好，也只能留给鸟雀。所以从跳下田到爬上来，中间不能断。

问：在香燃尽之前回到田埂，禾生最多能背回多少颗花生？

输入格式

第一行三个整数 $M,N,K$，以空格隔开，依次表示试验田的行数、列数，以及那截线香能烧的单位时间。

接下来 $M$ 行，每行 $N$ 个非负整数，以空格隔开。第 $i+1$ 行第 $j$ 个整数 $P_{i,j}$ 表示植株 $(i,j)$ 下结了多少颗花生；$0$ 表示这一株空着。

输出格式

一个整数：禾生最多能背回的花生数。

样例 #1

输入 #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

样例 #2

输入 #2

6 7 20
0 0 0 0 0 0 0
0 0 0 0 0 13 0 0

输出 #2

28

样例解释

以样例 #1 为例。田里结了花生的四株，从多到少依次是：

次序	位置	颗数
1	$(4,2)$	15
2	$(2,5)$	13
3	$(5,4)$	9
4	$(3,7)$	7

禾生先跳进 $(1,2)$，向下三步到 $(4,2)$，共 4 个单位时间，采摘又花 1 个，此时用了 5；转到 $(2,5)$ 走 5 步、采摘 1 步，此时 11；再转到 $(5,4)$ 走 4 步、采摘 1 步，此时 16；最后从 $(5,4)$ 向上四步回到第一行、跳回田埂，又花 5 个——正好 21。

背回 $15+13+9=37$ 颗。至于 $(3,7)$ 那七颗：从 $(5,4)$ 过去要 5 步，摘完再回埂要 3 步，前后就超了香的长度，只能留给鸟雀。

样例 #2 只少了一个单位时间：摘完 15 和 13 已用 11，从第二行回埂还要 2；若贪那九颗，回到埂上要 21，香恰好在这之前烧尽。所以禾生把篓子一收，答：28。

说明/提示

• 对于 $100\%$ 的数据，$1 \le M,N \le 20$，$0 \le K \le 1000$，$0 \le P_{i,j} \le 500$。
• 有花生的植株，其颗数两两不同。
• 注意：采摘途中不得回到田埂。

---

“这拨种子已经种下去了，等秋天的时候，你们就能看到结果了。”

——黍