问题描述

高桥君被神秘人物X带走，并被囚禁在一个神秘的设施中。这个设施的地板上有 $R$ 行 $C$ 列的方格，并且每个方格上都写着一个数字。高桥君位于方格的第一行第一列。

由于长时间被囚禁，高桥君开始感到饥饿。根据神秘人物X的说法，他将为高桥君准备一份与高桥君所在方格上的数字相同价值的章鱼烧，前提是高桥君必须移动恰好 $D$ 次。某个方格的“相邻方格”指的是与该方格共享边的方格。为了尽可能地吃到价值最高的章鱼烧，高桥君决定计算他最多能吃到多少价值的章鱼烧。

输入

输入从标准输入中按以下格式给出:

$R$ $C$ $D$ $A_{1,1}$ $A_{1,2}$ ... $A_{1,C}$ $A_{2,1}$ $A_{2,2}$ ... $A_{2,C}$ : $A_{R,1}$ $A_{R,2}$ ... $A_{R,C}$

• 第一行包含三个整数，$R (2 ≤ R ≤ 1,000)$ 表示方格的行数，$C (2 ≤ C ≤ 1,000)$ 表示方格的列数，$D (1 ≤ D ≤ 2,000)$ 表示高桥君需要移动的次数。
• 接下来的 $R$ 行给出了方格上的数字信息。其中第 $i$ 行包含 $C$ 个整数，用空格分隔。其中第 $j$ 个整数 $A_{i,j} (1 ≤ A_{i,j} ≤ 999)$ 表示方格第 $i$ 行第 $j$ 列上的数字为 $A_{i,j}$。

子任务

本题设有部分得分。

• 对于所有满足 $R ≤ 100$ 且 $C ≤ 100$ 且 $D ≤ 200$ 的测试用例，如果能够正确解答，则可得到60分。

输出

输出高桥君可以吃到的最大价值的章鱼烧的价格，在一行中输出，并在末尾添加换行符。

输入样例1

3 2 1
9 5
3 1
8 9

输出样例1

5

高桥君只需移动一次，可以到达的方格只有1行2列或者2行1列的方格。在这个例子中，高桥君最多可以吃到5元的章鱼烧。

输入样例2

4 4 100
999 999 999 999
999 999 999 999
999 999 999 999
999 999 999 999

输出样例2

999

在这个例子中，无论高桥君如何移动，他都可以吃到价值为999元的章鱼烧。

输入样例3

3 4 5
700 198 700 198
198 700 198 700
700 198 700 198

输出样例3

198

在这个例子中，无论高桥君如何移动，他只能吃到价值为198元的章鱼烧。