Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:256 MB

国家铁路

附加文件 统计

题目描述

dls的算竞王国可以被表示为一个有 $H$行和 $W$列的网格,我们让 $(i, j)$表示从北边第$i$行和从西边第$j$列的网格。最近此王国的公民希望国王能够修建一条铁路。

铁路的修建分为两个阶段:

  1. 从所有网格中挑选2个不同的网格,在这两个网格上分别修建一个火车站。在一个网络上修建一个火车站的代价是$A_{i,j}$。

  2. 在这两个网格间修建一条铁轨,假设我们选择的网格是 $(x_{1}, y_{1})$和$(x_{2}, y_{2})$,其代价是 $C \times (|x_{1} - x_{2}|+ |y_{1} - y_{2}|)$。

dls的愿望是希望用最少的花费去修建一条铁路造福公民们。现在请你求出这个最小花费。

题目输入

第一行输入三个整数分别代表$H, W, C (2\leq H, W \leq 1000, 1\leq C\leq 10^9)$。

接下来$H$行,每行$W$个整数,代表$A_{i, j} (1\leq A_{i, j}\leq 10^9)$。

题目输出

输出一个整数代表最小花费。

样例输入1

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

样例输出1

10

样例输入2

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

样例输出2

1001000001