← 返回题目列表

AtCoder · keyence2019_e

E. 连接城市

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

分数: 600 点

问题陈述

有 N AtCoder 共和国的城市。尺寸 i第城市是 A_{i}。 高桥想要建造 N-1 连接两个城市的双向道路,以便通过这些道路可以从任何其他城市到达任何城市。

假设修建一条连接 i第城市和 j第城市是 |i-j| \times D + A_{i} + A_{j}。 对于高桥来说,找到实现目标的最小可能总成本。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq A_{i} \leq 10^9
  • A_{i} 和 D 是整数。

输入

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

N D
A_1 A_2 ... A_N

输出

打印可能的最小总成本。


示例输入 1

3 1
1 100 1

示例输出 1

106

该成本可以通过例如修建连接城市的道路来实现 1, 2 和城市 1, 3.


示例输入 2

3 1000
1 100 1

示例输出 2

2202

示例输入 3

6 14
25 171 7 1 17 162

示例输出 3

497

示例输入 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

示例输出 4

658