103586: [Atcoder]ABC358 G - AtCoder Tour

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

问题描述

AtCoder 乐园是一个有 $H$ 行和 $W$ 列的网格。记 $(i, j)$ 为第 $i$ 行第 $j$ 列的单元格。

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

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

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

单元格 $(x', y')$ 只有当 $|x - x'| + |y - y'| = 1$ 时才被认为是单元格 $(x, y)$ 的相邻单元格。

限制条件

• $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$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$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

2 3 3
1 2
2 1 2
3 4 5

样例输出 1

14

Takahashi 可以通过以下方式获得总乐趣值 $14$：

• 最初，他在 $(1, 2)$。
• 他移动到单元格 $(2, 2)$。然后，他获得了乐趣值 $A_{2, 2} = 4$。
• 他移动到单元格 $(2, 3)$。然后，他获得了乐趣值 $A_{2, 3} = 5$。
• 他留在单元格 $(2, 3)$。然后，他获得了乐趣值 $A_{2, 3} = 5$。

他无法获得总乐趣值大于 $14$，所以打印 $14$。

样例输入 2

2 2 1000000000
2 1
100 100
100 99

样例输出 2

100000000000