You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Connecting Cities

题目描述

有 $n$ 个点排成一行，在第 $i,j$ 个点之间连边的代价为 $|i-j| \times D+A_i+A_j$，求将它们连成一棵树的最小代价。

输入格式

第一行两个整数 $n,D$。

第二行 $n$ 个整数 $A_1,A_2,\dots,A_n$。

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

3 1
1 100 1

样例输出 #1

106

样例 #2

样例输入 #2

3 1000
1 100 1

样例输出 #2

2202

样例 #3

样例输入 #3

6 14
25 171 7 1 17 162

样例输出 #3

497

样例 #4

样例输入 #4

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

样例输出 #4

658

数据范围

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ D\ \leq\ 10^9$
• $1\ \leq\ A_{i}\ \leq\ 10^9$