高桥王国可以用一个 $ 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}$。

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

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