AT_arc023_2.[ARC023B] 謎の人物X

高桥君被神秘人物 X 带走，并被关在了一个神秘的设施中。这个设施的地板上画有 $R$ 行 $C$ 列的格子，每个格子里写着一个数字。高桥君现在位于第 $1$ 行第 $1$ 列的格子。

由于被关了很久，高桥君已经饿了。根据神秘人物 X 的说法，“在恰好移动 $D$ 次到相邻格子后，高桥君所在格子上的数字就是他能吃到的章鱼烧的价格。”这里的“相邻格子”指的是与当前格子有公共边的格子。高桥君想吃到价格尽可能高的章鱼烧，请你帮他计算，他最多能吃到多少钱的章鱼烧。

输入以如下格式从标准输入读入。

$R$ $C$ $D$
$A_{1,1}$ $A_{1,2}$ ... $A_{1,C}$
$A_{2,1}$ $A_{2,2}$ ... $A_{2,C}$
$\vdots$
$A_{R,1}$ $A_{R,2}$ ... $A_{R,C}$

• 第 $1$ 行包含三个用空格分隔的整数，分别表示格子的行数 $R$（$2 \leq R \leq 1,000$）、列数 $C$（$2 \leq C \leq 1,000$）以及高桥君必须移动的步数 $D$（$1 \leq D \leq 2,000$）。
• 接下来的 $R$ 行，每行包含 $C$ 个用空格分隔的整数，表示每个格子上的数字。其中第 $i$ 行第 $j$ 个整数 $A_{i,j}$（$1 \leq A_{i,j} \leq 999$）表示第 $i$ 行第 $j$ 列格子上的数字。

输出高桥君能吃到的章鱼烧价格的最大值。输出后请换行。

部分分

本题设有部分分。

• 若你能通过所有满足 $R \leq 100$ 且 $C \leq 100$ 且 $D \leq 200$ 的测试点，将获得 $60$ 分。

样例解释 1

恰好移动 $1$ 次后能到达的格子只有第 $1$ 行第 $2$ 列和第 $2$ 行第 $1$ 列。在本例中，高桥君最多能吃到 $5$ 元的章鱼烧。

样例解释 2

在本例中，无论怎么移动，高桥君都能吃到 $999$ 元的章鱼烧。

样例解释 3

在本例中，无论怎么移动，高桥君最多只能吃到 $198$ 元的章鱼烧。

由 ChatGPT 4.1 翻译