国家铁路

题目描述

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