National Railway

题目描述

高橋王国は $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

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

1001000001

提示

$2 \leq H, W \leq 1000$ $1 \leq C \leq 10^9$ $1 \leq A_{ij} \leq 10^9$ 入力のすべての値は整数です。もしマス $(1, 1)$ と $(2, 3)$ に駅を建てると、駅の建設には $1 + 3 = 4$ 円かかり、線路の建設には $2 \times (|1-2| + |1-3|) = 6$ 円かかるので、合計で $4+6 = 10$ 円になります。 これは建設にかかる費用の総額の最小値です。

标签: AtCoder|abc210D

来源

AtCoder|abc210D