题目描述

Elly 最近了解到了保加利亚历史上的可汗——他们是游牧部族的统治者，在最终定居到如今保加利亚所在之地之前，曾在大陆上迁徙了数百年。

他们曾居住的大陆被划分为一个 $N\times M$ 的矩形网格区域，共有 $N\times M$ 个地区。可汗们每年会在某一个地区停留一年，并在这一年中消耗掉该地区的全部食物。到年末，他们会移动到与当前地区四联通相邻的某个地区，在那里度过下一年，并继续消耗全部食物，如此反复。我们认为这种移动在年末是瞬时发生的（与整整一年的时间相比，几天的旅程可以忽略不计）。可汗们不会在同一个地区连续停留两年，否则他们的部族会饿死。

每个地区都有一个它所能维持的最大食物量，记为整数 $A_{ij}$。

当可汗们把一个地区的食物吃光并离开后，该地区的食物会开始恢复。离开后的第一年初会恢复到 $1$ 单位；第二年翻倍；第三年再翻倍；……直到达到该地区的最大容量 $A_{ij}$ 为止。注意，食物量不会超过该地区的最大容量。

例如，若某个地区的最大食物量为 $A_{ij}=55$，那么在可汗离开后的接下来十年，每年年初该地区的食物量分别为：

$0,1,2,4,8,16,32,55,55,55$

可汗们知道，他们绝不能在某个地区食物尚未完全恢复到最大值之前回到那里，否则会对该地区造成永久破坏，这是他们不愿意做的。因此，有时他们宁可去一个当前食物较少、但已经恢复满的地区（例如 $42$），也不会去一个当前食物更多、却尚未完全恢复的地区（例如当前有 $64$，最大值是 $71$）。

在上面的例子中，他们最早可以在离开后的第 $8$ 年年初回到这个地区，因为这是它第一次恢复到最大值的时刻。

Elly 得到了整片大陆的信息，即一个有 $N$ 行 $M$ 列的矩阵 $A$，表示每个地区的最大食物量。初始时，每个地区都拥有其最大食物量。已知可汗们第一年在左上角地区停留，问：在持续 $K$ 年的前提下，他们最多总共能吃掉多少食物？

输入格式

第一行输入三个整数 $N$、$M$ 和 $K$，分别表示行数、列数和年数。

接下来 $N$ 行，每行输入 $M$ 个整数 $A_{ij}$，表示对应地区的最大食物量。

输出格式

输出一个整数，表示如果移动策略最优，可汗们最多能够消耗的食物总量。

数据范围

• $1 \le N,M \le 10$
• $1 \le K \le 100$
• $10 \le A_{ij} \le 100$

并保证始终存在一条路径，不会违反“不能进入尚未恢复满食物的地区”这一规则。

子任务

• $20\%$ 的测试满足 $1 \le N,M \le 4$
• 另外 $20\%$ 的测试满足 $1 \le K \le 20$

评分方式

每个测试点单独计分。

样例 1

输入

4 4 11
11 17 13 96
10 12 18 15
13 12 16 17
24 10 14 22

输出

254

样例 2

输入

7 10 27
92 33 98 66 51 65 50 28 17 65
81 26 35 90 51 79 16 49 26 68
94 16 61 45 20 31 99 75 51 73
17 83 11 75 59 56 15 24 63 44
83 32 80 49 60 83 85 98 17 76
16 75 81 97 89 50 80 34 79 64
26 64 59 37 14 30 20 58 46 66

输出

2017

样例解释

在第一个样例中，为了取得最大食物量 $254$，可汗们可以依次访问食物量为：

$11,17,13,96,15,17,22,14,16,18,15$

的地区。

在这条路径中，他们只会重复访问一个地区——最后那个食物量为 $15$ 的地区。

还需要注意的是：在最后一年结束后，周围相邻格子的食物都还没有恢复完成，因此可汗们无法继续移动。但这没有问题，因为这已经是最后一年了。

如果可汗们还需要再旅行一年（也就是 $K=12$ 而不是 $11$），那么他们就会选择另一条路线，因为停在原地不动不是一个允许的选项。此时，一条可行路径可以是：

$11,17,13,96,15,18,16,17,22,14,10,24$

其总和为 $273$。