分数: 400 点
问题陈述
高桥王国可以表示为一个网格 H 行和 W 列。让 (i, j) 表示位于 i从北数第 行, j从西数第 3 列。
最近,王国公民要求修建铁路的请求越来越多,现在国王高桥别无选择,只能修建一条铁路。
铁路建设将分以下两个阶段进行。
- 首先选择两个 不同 方格并在每个方格上建立一个车站。它的成本 A_{i,j} 日元在广场上建一个车站 (i, j).
- 然后,修建一条连接这两个车站的铁路轨道。这需要花费 C \times (|i-i'| + |j-j'|) 日元(当两个车站位于广场上时) (i, j) 和 (i', j'). (|x| 表示绝对值 x.)
高桥的首要任务是尽可能少地在这项建设上花费,而不是改善公民的便利。
打印铁路建设的最低可能总成本。
约束
- 2 \leq H, W \leq 1000
- 1 \leq C \leq 10^9
- 1 \leq A_{ij} \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W C
A_{1,1} A_{1,2} \cdots A_{1,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
输出
打印铁路建设的最低可能总成本。
示例输入 1
3 4 2 1 7 7 9 9 6 3 7 7 8 6 4
示例输出 1
10
如果我们在广场上建车站 (1, 1) 和 (2, 3),这将花费 1 + 3 = 4 日元建造车站和 2 \times (|1-2| + |1-3|) = 6 日元建造赛道,总计 4+6 = 10 日元。 这是建筑的最低可能总成本。
示例输入 2
3 3 1000000000 1000000 1000000 1 1000000 1000000 1000000 1 1000000 1000000
示例输出 2
1001000001