Score : 600 points
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.
Input is given from Standard Input in the following format:
N D A_1 A_2 ... A_N
Print the minimum possible total cost.
3 1 1 100 1
106
This cost can be achieved by, for example, building roads connecting City 1, 2 and City 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