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;
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
typedef pair<LL,int> PII;
const int N=200010;
const LL inf=1e18;
int n,D,s[N];
struct node{
	int x,y;
	PII p; LL s;
	PII s1[2],s2[2];
}a[N*5];
void pushup(int t){
	int l=t<<1,r=l|1;PII pp;LL ss;
	ref(d,0,1)a[t].s1[d]=min(a[l].s1[d],a[r].s1[d]);
	ref(d,0,1)a[t].s2[d]=min(a[l].s2[d],a[r].s2[d]);
	if(a[l].s<a[r].s) a[t].p=a[l].p,a[t].s=a[l].s;
		else a[t].p=a[r].p,a[t].s=a[r].s;
	pp=mp(a[l].s2[0].se,a[r].s1[1].se);
	ss=a[l].s2[0].fi+a[r].s1[1].fi;
	if(ss<a[t].s)a[t].p=pp,a[t].s=ss;
	pp=mp(a[r].s1[0].se,a[l].s2[1].se);
	ss=a[l].s2[1].fi+a[r].s1[0].fi;
	if(ss<a[t].s)a[t].p=pp,a[t].s=ss;
}
void build(int x,int y,int t){
	a[t].x=x;a[t].y=y;
	if(x==y){
		a[t].p=mp(0,0); a[t].s=inf;
		a[t].s1[0]=mp(s[x]+(LL)D*x,x);a[t].s1[1]=mp(inf,0);
		a[t].s2[0]=mp(s[x]-(LL)D*x,x);a[t].s2[1]=mp(inf,0);
		return;
	}
	int m=(x+y)>>1;
	build(x,m,t<<1);
	build(m+1,y,t<<1|1);
	pushup(t);
}
void update(int x,int y,int t,int p){
	if(x==y){
		swap(a[t].s1[0],a[t].s1[1]);
		swap(a[t].s2[0],a[t].s2[1]);
		return;
	}
	int m=(x+y)>>1;
	if(p<=m)update(x,m,t<<1,p);
	else update(m+1,y,t<<1|1,p);
	pushup(t);
}
int main(){
	cin>>n>>D;
	ref(i,1,n)cin>>s[i];
	build(1,n,1);
	update(1,n,1,1);
	LL ans=0;
	ref(i,1,n-1){
		PII p=a[1].p;LL s=a[1].s;
		update(1,n,1,p.fi);ans+=s;
	}
	cout<<ans<<endl;
}