题目描述

高橋王国は $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$ の絶対値を表す。）

高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています。
鉄道建設にかかる費用として考えられる最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

鉄道建設にかかる費用として考えられる最小値を出力せよ。

题目大意

题目翻译

国王想在他 $H$ 行 $W$ 列的国土上建铁路
具体地，建铁路的花费可以表示为两部分：建车站和建轨道。

• 在 $(i,\ j)$ 处建车站的费用表示为 $A_{i,j}$
• 连接 $(i,\ j)$ 处的车站和 $(i',\ j')$ 处车站之间铁路的花费为 $C\ \times\ (|i-i'|\ +\ |j-j'|)$

由于不修铁路会下台，而国王又没有太多钱，所以想知道在不考虑便利性的前提下修铁路的最小花费。

输入格式

第一行三个整数 $H$ $W$ $C$
接下来 $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$
• 入力はすべて整数

Sample Explanation 1

マス $(1,\ 1)$ とマス $(2,\ 3)$ に駅を建設すると、駅の建設費用が $1\ +\ 3\ =\ 4$ 円、 線路の建設費用が $2\ \times\ (|1-2|\ +\ |1-3|)\ =\ 6$ 円となり、鉄道建設にかかる費用は $4+6\ =\ 10$ 円となります。 これが費用として考えられる最小値です。