H - Takahashi is Slime 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

縦 H 行横 W 列のマス目があります。 上から i 行目 (1\leq i\leq H)、左から j 列目 (1\leq j\leq W) のマスをマス (i,j) と呼ぶことにします。

はじめ、マス (i,j) には強さ S _ {i,j} のスライムがおり、マス (P,Q) にいるスライムが高橋くんです。

高橋くんが以下の行動を好きな回数（0 回でもよい）行ったあとの、高橋くんの強さとしてありえる最大値を求めてください。

  • 高橋くんに隣接するスライムのうち、強さが高橋くんの強さの \dfrac1X 倍未満のものを選んで吸収する。 その結果、吸収されたスライムは消滅し、高橋君の強さは吸収したスライムの強さだけ増加する。

上記の行動の際、スライムが吸収され消滅したことで生じた隙間は直ちに高橋くんによって埋められ、消滅したスライムに隣接していたスライム（それらが存在すれば）は新たに高橋くんと隣接します（入出力例１の説明も参照してください）。

制約

  • 1\leq H,W\leq500
  • 1\leq P\leq H
  • 1\leq Q\leq W
  • 1\leq X\leq10^9
  • 1\leq S _ {i,j}\leq10^{12}
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

H W X 
P Q
S _ {1,1} S _ {1,2} \ldots S _ {1,W}
S _ {2,1} S _ {2,2} \ldots S _ {2,W}
\vdots
S _ {H,1} S _ {H,2} \ldots S _ {H,W}

出力

高橋くんが行動を行ったあとの高橋くんの強さとしてありえる最大値を出力せよ。

入力例 1

3 3 2
2 2
14 6 9
4 9 20
17 15 7

出力例 1

28

はじめ、それぞれのマスにいるスライムの強さは以下の図のようになっています。

例えば、高橋くんは次のように行動を行うことができます。

  • マス (2,1) にいるスライムを吸収する。高橋くんの強さは 9+4=13 となり、新たにマス (1,1) のスライムとマス (3,1) のスライムが高橋くんと隣接する。
  • マス (1,2) にいるスライムを吸収する。高橋くんの強さは 13+6=19 となり、新たにマス (1,3) のスライムが高橋くんと隣接する。
  • マス (1,3) にいるスライムを吸収する。高橋くんの強さは 19+9=28 となる。

以上の行動を行ったあと、高橋くんの強さは 28 となります。

高橋くんがどのように行動を行っても、高橋くんの強さを 28 より大きくすることはできないため、28 を出力してください。

高橋くんの強さの \dfrac12 倍未満のスライムしか吸収できないことに注意してください。 例えば、上図の右側の状態からマス (1,1) にいるスライムを吸収することはできません。

入力例 2

3 4 1
1 1
5 10 1 1
10 1 1 1
1 1 1 1

出力例 2

5

高橋くんはどのスライムも吸収できません。

入力例 3

8 10 2
1 5
388 130 971 202 487 924 247 286 237 316
117 166 918 106 336 928 493 391 235 398
124 280 425 955 212 988 227 222 307 226
336 302 478 246 950 368 291 236 170 101
370 200 204 141 287 410 388 314 205 460
291 104 348 337 404 399 416 263 415 339
105 420 302 334 231 481 466 366 401 452
119 432 292 403 371 417 351 231 482 184

出力例 3

1343

Score : 450 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the cell at the i-th row (1\leq i\leq H) from the top and j-th column (1\leq j\leq W) from the left.

Initially, there is a slime with strength S _ {i,j} in cell (i,j), and Takahashi is the slime in the cell (P,Q).

Find the maximum possible strength of Takahashi after performing the following action any number of times (possibly zero):

  • Among the slimes adjacent to him, choose one whose strength is strictly less than \dfrac{1}{X} times his strength and absorb it. As a result, the absorbed slime disappears, and Takahashi's strength increases by the strength of the absorbed slime.

When performing the above action, the gap left by the disappeared slime is immediately filled by Takahashi, and the slimes that were adjacent to the disappeared one (if any) become newly adjacent to Takahashi (refer to the explanation in sample 1).

Constraints

  • 1\leq H,W\leq500
  • 1\leq P\leq H
  • 1\leq Q\leq W
  • 1\leq X\leq10^9
  • 1\leq S _ {i,j}\leq10^{12}
  • All input values are integers.

Input

The input is given in the following format from Standard Input:

H W X 
P Q
S _ {1,1} S _ {1,2} \ldots S _ {1,W}
S _ {2,1} S _ {2,2} \ldots S _ {2,W}
\vdots
S _ {H,1} S _ {H,2} \ldots S _ {H,W}

Output

Print the maximum possible strength of Takahashi after performing the action.

Sample Input 1

3 3 2
2 2
14 6 9
4 9 20
17 15 7

Sample Output 1

28

Initially, the strength of the slime in each cell is as follows:

For example, Takahashi can act as follows:

  • Absorb the slime in cell (2,1). His strength becomes 9+4=13, and the slimes in cells (1,1) and (3,1) become newly adjacent to him.
  • Absorb the slime in cell (1,2). His strength becomes 13+6=19, and the slime in cell (1,3) becomes newly adjacent to him.
  • Absorb the slime in cell (1,3). His strength becomes 19+9=28.

After these actions, his strength is 28.

No matter how he acts, it is impossible to get a strength greater than 28, so print 28.

Note that Takahashi can only absorb slimes whose strength is strictly less than half of his strength. For example, in the figure on the right above, he cannot absorb the slime in cell (1,1).

Sample Input 2

3 4 1
1 1
5 10 1 1
10 1 1 1
1 1 1 1

Sample Output 2

5

He cannot absorb any slimes.

Sample Input 3

8 10 2
1 5
388 130 971 202 487 924 247 286 237 316
117 166 918 106 336 928 493 391 235 398
124 280 425 955 212 988 227 222 307 226
336 302 478 246 950 368 291 236 170 101
370 200 204 141 287 410 388 314 205 460
291 104 348 337 404 399 416 263 415 339
105 420 302 334 231 481 466 366 401 452
119 432 292 403 371 417 351 231 482 184

Sample Output 3

1343