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 pair<long,long> P;
typedef pair<long,P> PP;

vector<PP> edge;
long long N,D;
vector<long long> A;
const long INF=(1L<<50);
class UF{
  vector<int> par,rank;
public:
  UF(int size){
    par.resize(size);rank.resize(size);
    for (int i = 0; i < size; i++) {
      par[i]=i;
      rank[i]=0;
    }
  }
  int find(int x){
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }
  void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])par[x]=y;
    else{
      par[y]=x;
      if(rank[x]==rank[y])rank[x]++;
    }
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
};


void solve(long l,long r){
    if(l==r)return;
    long m=(l+r)/2;
    long mn=INF;
    int pl=-1;
    for(long i = l; i <= m; i++)
    {
        long vl=A[i]-D*i;
        if(mn>vl){
            mn=vl;
            pl=i;
        }
    }
    long pr=-1;
    mn=INF;
    for(long i=m+1;i<=r;i++){
        long vr=A[i]+D*i;
        if(mn>vr){
            mn=vr;
            pr=i;
        }
    }
    for(long i = l; i <= m; i++)
    {
        edge.push_back(PP(A[i]+A[pr]+D*(pr-i),P(i,pr)));
    }
    for(long i = m+1; i < r+1; i++)
    {
        edge.push_back(PP(A[i]+A[pl]+D*(i-pl),P(pl,i)));
    }
    solve(l,m);
    solve(m+1,r);
    return;
}


int main(){
    scanf("%lld",&N);
    scanf("%lld",&D);
    A.resize(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(0,N-1);
    sort(edge.begin(),edge.end());
    UF uf(N);
    long ret=0;
    for(auto tmp:edge){
        P p=tmp.second;
        if(!uf.same(p.first,p.second)){
            uf.unite(p.first,p.second);
            ret+=tmp.first;
        }
    }
    cout<<ret<<endl;
    return 0;
}
