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.

Examples

Input

3 1
1 100 1


Output

106


Input

3 1000
1 100 1


Output

2202


Input

6 14
25 171 7 1 17 162


Output

497


Input

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


Output

658
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
 
const int MAXN = 400100;
vector<PII> graph[MAXN];
 
void add_edge(int v, int u, int c) {
  graph[v].push_back(PII(u,c));
  graph[u].push_back(PII(v,c));
}
 
 
int main() {
  int N, D;
  cin >> N >> D;
  for(int i=0; i<N; i++) {
    LL p;
    cin >> p;
    add_edge(i, i+N, p);
  }
 
  for(int i=0; i<N-1; i++) {
    int v,u,c;
    //cin >> v >> u >> c;
    //v--;u--;
    add_edge(i, i+1, D);
  }
 
  priority_queue<pair<LL,PII> , vector<pair<LL,PII> >, greater<pair<LL,PII> > > pq;
  vector<int> used(2*N, 0), dist(2*N, 0);
  int cnt = 1;
  LL ans = 0;
  for(int i=0; i<N; i++) {
    pq.push(make_pair(0, PII(i+N, -1)));
  }
  while(!pq.empty()) {
    auto cur = pq.top(); pq.pop();
    LL v = cur.second.first;
    if(used[v]) {
      LL u = cur.second.second;
      if(used[v] > used[u])
	ans += dist[v] + cur.first;
      continue;
    }
    used[v] = cnt;
    cnt++;
    dist[v] = cur.first;
    for(auto uc: graph[v]) {
      LL u = uc.first;
      LL c = uc.second;
      pq.push(make_pair(dist[v] + c, PII(u, v)));
    }
    
  }
  cout << ans << endl;
  
  return 0;
}