AtCoder 之旅

题目描述

AtCoder Land 用 $H$ 行 $W$ 列的网格表示。设 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

高桥从格子 $(S_i, S_j)$ 出发，重复以下行动 $K$ 次：

他要么停留在当前格子，要么移动到相邻格子。完成这次行动后，如果他在格子 $(i, j)$，他将获得 $A_{i, j}$ 的趣味值。

求他最多能获得的总趣味值。

这里，格子 $(x', y')$ 与格子 $(x, y)$ 相邻，当且仅当 $|x - x'| + |y - y'| = 1$。

输入格式

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

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

输出格式

输出答案。

样例

2 3 3
1 2
2 1 2
3 4 5

14

高桥可以如下行动，获得总趣味值 $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 1000000000
2 1
100 100
100 99

100000000000

数据范围

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