题目描述

高桥王国可以表示为一个 $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}$

输出

打印修建铁路的最小可能总成本。

示例输入 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