/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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}
出力
鉄道建設にかかる費用として考えられる最小値を出力せよ。
入力例 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
Score : 400 points
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