/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
コストの総和のあり得る最小値を出力せよ．
入力例 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
Score : 600 points
Problem Statement
There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}. Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.
Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}. For Takahashi, find the minimum possible total cost to achieve the objective.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 10^9
- 1 \leq A_{i} \leq 10^9
- A_{i} and D are integers.
Input
Input is given from Standard Input in the following format:
N D A_1 A_2 ... A_N
Output
Print the minimum possible total cost.
Sample Input 1
3 1 1 100 1
Sample Output 1
106
This cost can be achieved by, for example, building roads connecting City 1, 2 and City 1, 3.
Sample Input 2
3 1000 1 100 1
Sample Output 2
2202
Sample Input 3
6 14 25 171 7 1 17 162
Sample Output 3
497
Sample Input 4
12 5 43 94 27 3 69 99 56 25 8 15 46 8
Sample Output 4
658