配点 : $600$ 点

問題文

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

$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$

出力

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

3 1
1 100 1

106

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

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