分数: 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