AT_abc210_d [ABC210D] National Railway

题目描述

高桥王国可以用一个 $H$ 行 $W$ 列的网格表示。用 $(i, j)$ 表示从北边数第 $i$ 行、从西边数第 $j$ 列的格子。

最近，王国内要求修建铁路的公民呼声越来越高，国王高桥君别无选择，必须修建一条铁路。铁路的修建包含以下两个阶段：

• 首先，选择两个不同的格子，并在每个格子上修建一个车站。在格子 $(i, j)$ 上修建车站需要花费 $A_{i,j}$ 日元。
• 然后，修建一条连接这两个车站的铁路轨道。当两个车站分别位于格子 $(i, j)$ 和 $(i', j')$ 时，修建轨道的费用为 $C \times (|i - i'| + |j - j'|)$ 日元。（$|x|$ 表示 $x$ 的绝对值。）

高桥君的首要目标是尽可能减少修建铁路的总费用，而不是提高公民的便利性。

请输出修建铁路可能的最小总费用。

输入格式

第一行，三个整数 $H,W,C$。

接下来 $H$ 行 $W$ 列，表示在各地建车站的费用 $A_{i,j}$。

输出格式

共一行一个整数，表示最小花费。

样例 1

输入

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

输出

10

样例 2

输入

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

输出

1001000001

说明/提示

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

Translated by Deepseek.