D - 国家铁路

分数：$400$ 分

问题描述

高桥王国可以表示为一个有 $H$ 行 $W$ 列的网格。$(i, j)$ 表示从北边数第 $i$ 行、从西边数第 $j$ 列的方块。

最近，王国的市民对修建一条铁路的要求越来越多，现在高桥王不得不修建一条铁路。
铁路的建设将分为以下两个阶段。

• 首先，选择两个不同的方块，在每个方块上建立一个车站。在方块 $(i, j)$ 上建立一个车站需要花费 $A_{i,j}$ 日元。
• 然后，建造一段连接这两个车站的铁路轨道。当这两个车站位于方块 $(i, j)$ 和 $(i', j')$ 时，需要花费 $C \times (|i-i'| + |j-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}$

输出

输出修建铁路的最小总花费。

3 4 2
1 7 7 9
9 6 3 7
7 8 6 4

10

如果我们在方块 $(1, 1)$ 和 $(2, 3)$ 上建立车站，那么建造车站的花费将为 $1 + 3 = 4$ 日元，建造轨道的花费将为 $2 \times (|1-2| + |1-3|) = 6$ 日元，总共为 $4+6 = 10$ 日元。 这是修建铁路的最小总花费。

3 3 1000000000
1000000 1000000 1
1000000 1000000 1000000
1 1000000 1000000

1001000001