← 返回题目列表

AtCoder · abc210_d

D. 国家铁路

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

高桥王国可以表示为一个网格 H 行和 W 列。让 (i, j) 表示位于 i从北数第 行, j从西数第 3 列。

最近,王国公民要求修建铁路的请求越来越多,现在国王高桥别无选择,只能修建一条铁路。
铁路建设将分以下两个阶段进行。

  • 首先选择两个 不同 方格并在每个方格上建立一个车站。它的成本 A_{i,j} 日元在广场上建一个车站 (i, j).
  • 然后,修建一条连接这两个车站的铁路轨道。这需要花费 C \times (|i-i'| + |j-j'|) 日元(当两个车站位于广场上时) (i, j) 和 (i', j'). (|x| 表示绝对值 x.)

高桥的首要任务是尽可能少地在这项建设上花费,而不是改善公民的便利。
打印铁路建设的最低可能总成本。

约束

  • 2 \leq H, W \leq 1000
  • 1 \leq C \leq 10^9
  • 1 \leq A_{ij} \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W C
A_{1,1} A_{1,2} \cdots A_{1,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}

输出

打印铁路建设的最低可能总成本。


示例输入 1

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

示例输出 1

10

如果我们在广场上建车站 (1, 1) 和 (2, 3),这将花费 1 + 3 = 4 日元建造车站和 2 \times (|1-2| + |1-3|) = 6 日元建造赛道,总计 4+6 = 10 日元。 这是建筑的最低可能总成本。


示例输入 2

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

示例输出 2

1001000001