← 返回题目列表

AtCoder · abc358_g

G. AtCoder 之旅

中文机器翻译题面 查看原题

分数: 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