/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
Score : 550 points
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