Score : $550$ points

问题陈述

AtCoder Land 由一个 $H$ 行 $W$ 列的网格表示。用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的单元格。

高桥从单元格 $(S_i, S_j)$ 开始，重复以下动作 $K$ 次：

• 他要么留在当前单元格，要么移动到相邻单元格。在执行这个动作后，如果他在单元格 $(i, j)$，他将获得一个乐趣值 $A_{i, j}$。

找出他可以获得的最大总乐趣值。

这里，如果 $|x - x'| + |y - y'| = 1$，则认为单元格 $(x', y')$ 与单元格 $(x, y)$ 相邻。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

AtCoder Land is represented by a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row and $j$-th column.

Takahashi starts at cell $(S_i, S_j)$ and repeats the following action $K$ times:

• He either stays in the current cell or moves to an adjacent cell. After this action, if he is in cell $(i, j)$, he gains a fun value of $A_{i, j}$.

Find the maximum total fun value he can gain.

Here, a cell $(x', y')$ is considered adjacent to cell $(x, y)$ if and only if $|x - x'| + |y - y'| = 1$.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print the answer.

Sample Input 1

2 3 3
1 2
2 1 2
3 4 5

Sample Output 1

14

Takahashi can gain a total fun value of $14$ by acting as follows:

• Initially, he is at $(1, 2)$.
• He moves to cell $(2, 2)$. Then, he gains a fun value of $A_{2, 2} = 4$.
• He moves to cell $(2, 3)$. Then, he gains a fun value of $A_{2, 3} = 5$.
• He stays in cell $(2, 3)$. Then, he gains a fun value of $A_{2, 3} = 5$.

He cannot gain a total fun value greater than $14$, so print $14$.

Sample Input 2

2 2 1000000000
2 1
100 100
100 99

Sample Output 2

100000000000