AT_abc210_d [ABC210D] National Railway

题目描述

题目翻译

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

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

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

输入格式

第一行三个整数 $H$ $W$ $C$
接下来 $H$ 行 $W$ 列表示在各地建车站的费用

输出格式

最小花费

输入输出样例 #1

输入 #1

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

输出 #1

10

输入输出样例 #2

输入 #2

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

输出 #2

1001000001

说明/提示

• $2\le H,W\le 1000$
• $1\le C\le10^9$
• $1\le A_{i,j}\le 10^9$
• 所有输入均为整数。