AT_abc358_g [ABC358G] AtCoder Tour

AtCoder Land 由 $H$ 行 $W$ 列的网格组成。从上往下第 $i$ 行，从左往右第 $j$ 列的格子记作 $(i, j)$。 高桥君一开始在格子 $(S_i, S_j)$，他会重复进行 $K$ 次如下操作： - 高桥君可以选择留在当前位置，或者移动到相邻的格子。之后，他会获得当前所在格子的 $A_{i, j}$ 的乐趣值。 请你求出高桥君能够获得的乐趣值总和的最大值。 这里，相邻的格子指的是满足 $|x - x'| + |y - y'| = 1$ 的格子 $(x', y')$。

输入按以下格式从标准输入给出。 > $H$ $W$ $K$ $S_i$ $S_j$ $A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$

请输出答案。

### 限制条件 - $1 \leq H, W \leq 50$ - $1 \leq K \leq 10^9$ - $1 \leq S_i \leq H$ - $1 \leq S_j \leq W$ - $1 \leq A_{i, j} \leq 10^9$ - 输入的所有值均为整数 ### 样例解释 1 高桥君可以按如下方式行动，使乐趣值总和达到 $14$： - 一开始，高桥君在 $(1, 2)$。 - 高桥君移动到格子 $(2, 2)$，获得 $A_{2, 2} = 4$ 的乐趣值。 - 高桥君移动到格子 $(2, 3)$，获得 $A_{2, 3} = 5$ 的乐趣值。 - 高桥君留在格子 $(2, 3)$，获得 $A_{2, 3} = 5$ 的乐趣值。 高桥君无法获得比 $14$ 更大的乐趣值，因此输出 $14$。 由 ChatGPT 4.1 翻译