分数: 450 点
问题陈述
有一个网格 H 水平行和 W 垂直列。 让 (i, j) 表示位于 i第行 (1\leq i\leq H) 从顶部和 j第列 (1\leq j\leq W) 从左边开始。
最初有一个有力量的史莱姆 单元格中的 S _ {i,j} 在细胞内 (i,j),高桥是牢房里的粘液 (P,Q).
执行以下操作任意次数(可能为零)后,求高桥的最大可能力量:
- 在与他相邻的史莱姆中,选择一个力量为 严格小于 \dfrac{1}{X} 乘以他的力量并吸收它。 结果,吸收的粘液消失,高桥的力量随着吸收的粘液的强度而增加。
当执行上述动作时,消失的史莱姆留下的间隙会立即被高桥填补,并且与消失的史莱姆(如果有的话)相邻的史莱姆会重新与高桥相邻(参见样本1中的解释)。
约束
- 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.
请注意,高桥只能吸收力量严格小于他力量一半的史莱姆。比如右上图中,他无法吸收细胞内的粘液 (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