分数: 550 点
问题陈述
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.
约束
- 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
高桥可以获得的总乐趣值 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