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<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,d,a[N],fa[N],t;
ll ans;
struct data
{
	int x,y;ll z;
	bool operator <(const data&a) const
	{
		return z<a.z;
	}
}e[N<<5];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
ll calcl(int i)
{
	return a[i]-1ll*i*d;
}
ll calcr(int i)
{
	return a[i]+1ll*i*d;
}
void solve(int l,int r)
{
	if (l==r) return;
	int mid=l+r>>1;
	solve(l,mid);
	solve(mid+1,r);
	int L=l;
	for (int i=l;i<=mid;i++) if (calcl(i)<calcl(L)) L=i;
	int R=r;
	for (int i=mid+1;i<=r;i++) if (calcr(i)<calcr(R)) R=i;
	for (int i=l;i<=mid;i++) e[++t]=(data){i,R,calcl(i)+calcr(R)};
	for (int i=mid+1;i<=r;i++) e[++t]=(data){L,i,calcl(L)+calcr(i)};
}
signed main()
{
	n=read(),d=read();
	for (int i=1;i<=n;i++) a[i]=read();
	solve(1,n);
	for (int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+t+1);
	for (int i=1;i<=t;i++)
	if (find(e[i].x)!=find(e[i].y))
	{
		fa[find(e[i].x)]=find(e[i].y);
		ans+=e[i].z;
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}