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;
#define inf 0x3f3f3f3f3f3f3f3f
const int maxn=2e5+10;
ll A[maxn];
ll D;
struct Edge
{
	int u,v;
	ll cst;
	Edge(){}
	Edge(int u,int v,ll cst):u(u),v(v),cst(cst){}
	bool operator < (const Edge &t)const
	{
		return cst<t.cst;
	}
};
vector<Edge> edge;
void solve(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	
	int v1=0;
	ll mn=inf;
	for(int i=l;i<=mid;i++)
	{
		ll vl=A[i]-D*1ll*i;
		if(vl<mn)
		{
			mn=vl;
			v1=i;
		}
	}
	
	int v2=0;
	mn=inf;
	
	for(int i=mid+1;i<=r;i++)
	{
		ll vl=A[i]+D*1ll*i;
		if(vl<mn)
		{
			mn=vl;
			v2=i;
		}
	}
	
	for(int i=l;i<=mid;i++)
	{
	//	cout<<(A[v2]+A[i]+D*(v2-i))<<" "<<v2<<" "<<i<<endl;
		edge.push_back(Edge(v2,i,A[v2]+A[i]+D*1ll*(v2-i)));
	}
	
	for(int i=mid+1;i<=r;i++)
	{
	//	cout<<(A[v1]+A[i]+D*(i-v1))<<" "<<i<<" "<<v1<<endl;
		edge.push_back(Edge(v1,i,A[v1]+A[i]+D*1ll*(i-v1)));
	}
//	system("pause");
	
	solve(l,mid);
	solve(mid+1,r);
}
int fa[maxn];
inline int getfa(int x)
{
	return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
int main()
{
	int n;
	scanf("%d%lld",&n,&D);
	for(int i=0;i<n;i++)scanf("%lld",&A[i]);
	
	solve(0,n-1);
	
	sort(edge.begin(),edge.end()); 
	
	for(int i=0;i<n;i++)fa[i]=i; 
	ll ans=0;
	for(int i=0;i<edge.size();i++)
	{
		int u=edge[i].u,v=edge[i].v;
		if(getfa(u)==getfa(v))continue;
	//	cout<<u<<" "<<v<<endl;
		fa[getfa(u)]=getfa(v);
		ans+=edge[i].cst;
	}
	printf("%lld\n",ans);
	return 0;
}