题目描述

A 市为了庆祝中秋节，计划在城市的各个角落建设赏月打卡点，并考虑在两个特定的打卡点之间建立一条特殊的“月光桥”，以便市民们能够更方便地欣赏到不同地点的美景。假设把 A 市看成一个 $W×H$ 的网格，那么每个打卡点都位于一个上的特定位置 $(i,j)$。

在建立“月光桥”之前，人们只能通过网格图上原有的路径来移动。但现在，为了提升节日氛围，政府决定修建一条这样的桥。然而，由于预算有限，政府只想修建一条桥，并希望知道修建这条桥的最小成本。

修建“月光桥”的步骤如下：首先，选择两个不同的打卡点位置 $(i,j),(i',j')$，这两个位置需要分别支付 $A_{i,j},A_{i',j'}$ 的费用来准备桥的基础建设。然后，需要连接这两个位置，连接的费用是 $C \times (|i-i'|+|j-j'|)$，这代表了铺设桥面和支撑结构的成本。因此，修建“月光桥”的总成本是 $A_{i,j} + A_{i', j'} + C\times (|i-i'|+|j-j'|)$。

输入格式

第一行输入三个整数 $W,H,C$，其含义如题面所示。

接下来 $W$ 行每行输入 $H$ 个整数 $A_{i,j}$，表示在 $(i,j)$ 位置准备桥基础建设的费用。

输出格式

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

样例输入

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

样例输出

10

样例解释

选择 $(1,1)$ 与 $(2,3)$ 之间建设月光桥，那么花费就是 $1 + 3 + 2 \times 3 = 10$。

数据范围

• 对于 100% 的数据，$2 \le W,H \le 1000,1\le C, A_{i,j} \le 10^9$