题目描述

AtCoder国には $N$ 個の都市があります．$i$ 番目の都市の規模は $A_{i}$ です． 高橋君は，$2$ 都市間を双方向に結ぶ道路を $N-1$ 本建設することで $N$ 個の都市のどの $2$ つを取っても互いに道路を通り行き来できるようにしたいです．

$i$ 番目の都市と $j$ 番目の都市を結ぶ道路の建設コストが $|i-j|\ \times\ D\ +\ A_{i}\ +\ A_{j}$ であるとします． 高橋君のために，目標を達成するためのコストの総和のあり得る最小値を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $D$ $A_1$ $A_2$ $...$ $A_N$

输出格式

コストの総和のあり得る最小値を出力せよ．

题目大意

题目描述

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

$1 \leq n \leq 10^5$，$1 \leq D,A_i \leq 10^9$

输入格式

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

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

输出格式

输出一个整数表示答案。

3 1
1 100 1

106

3 1000
1 100 1

2202

6 14
25 171 7 1 17 162

497

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

658

提示

制約

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

Sample Explanation 1

例えば，都市 $1$ と都市 $2$ の間と，都市 $1$ と都市 $3$ の間に道路を建設することで，このコストを達成することができます．