国营铁路

题目描述

高桥王国可以用一个 $H$ 行 $W$ 列的网格表示。设 $(i, j)$ 表示从北数第 $i$ 行、从西数第 $j$ 列的格子。

最近,王国国民要求修建铁路的呼声越来越高,国王高桥君不得不修建一条铁路。

铁路的建设分为以下两个阶段。

首先,选择两个不同的格子,并在每个格子上修建车站。在格子 $(i, j)$ 上修建车站需要花费 $A_{i,j}$ 日元。

然后,修建连接这两个车站的铁路轨道。当两个车站分别位于格子 $(i, j)$ 和 $(i', j')$ 时,花费 $C \times (|i-i'| + |j-j'|)$ 日元。($|x|$ 表示 $x$ 的绝对值。)

比起改善国民的便利性,高桥君更注重尽量降低建设成本。

输出铁路建设总费用的最小值。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $2 \le H, W \le 1000$
• $1 \le C \le 10^9$
• $1 \le A_{ij} \le 10^9$
• 输入均为整数