102103: [AtCoder]ABC210 D - National Railway

Problem Statement

The Kingdom of Takahashi can be represented as a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$-th row from the north and $j$-th column from the west.

Recently, there have been more and more requests from the kingdom's citizens to build a railway, and now the king, Takahashi, has no choice but to build one.
The construction of the railway will have the following two phases.

• First, choose two different squares and build a station on each of them. It costs $A_{i,j}$ yen to build a station on the square $(i, j)$.
• Then, build a railway track connecting these two stations. This costs $C \times (|i-i'| + |j-j'|)$ yen when the two stations are on the squares $(i, j)$ and $(i', j')$. ($|x|$ denotes the absolute value of $x$.)

Takahashi's priority is to spend as little as possible on this construction, rather than to improve convenience for the citizens.
Print the minimum possible total cost of the construction of the railway.

Constraints

• $2 \leq H, W \leq 1000$
• $1 \leq C \leq 10^9$
• $1 \leq A_{ij} \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$ $C$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$

Output

Print the minimum possible total cost of the construction of the railway.

Sample Input 1

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

Sample Output 1

10

If we build stations on the squares $(1, 1)$ and $(2, 3)$, it will cost $1 + 3 = 4$ yen to build the stations and $2 \times (|1-2| + |1-3|) = 6$ yen to build the track, for a total of $4+6 = 10$ yen. This is the minimum possible total cost of the construction.

Sample Input 2

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

Sample Output 2

1001000001

问题描述

塔卡哈希王国可以用一个有$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