配点 : $400$ 点

問題文

高橋王国は $H$ 行 $W$ 列のグリッドで表されます。北から $i$ 行目、西から $j$ 列目のマスを $(i, j)$ で表します。

このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。 鉄道建設は以下の $2$ つのステップからなります。

• まず、$2$ つの異なるマスを選び、それぞれに駅を建設する。マス $(i, j)$ に駅を建設すると $A_{i,j}$ 円の費用がかかる。
• その後、建設した $2$ つの駅を結ぶ線路を建設する。$2$ つの駅がマス $(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