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
/* --- author: dxm --- */
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

void qread(int &x){
	int neg=1;x=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
	while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
	x*=neg;
}

const int maxn=200005;
int n,d,tot;
int a[maxn];
ll ans;
class Edge{
public:
	int u,v;
	ll w;
	Edge(int _u=0,int _v=0,ll _w=0):u(_u),v(_v),w(_w){}
	bool operator < (const Edge &o)const{
		return w<o.w;
	}
}e[maxn*20];

namespace Dsu{
	int f[maxn];
	void init(){
		REP(i,n)f[i]=i;
	}
	int find(int x){
		return f[x]==x?x:f[x]=find(f[x]);
	}
}

void solve(int l,int r){
	if(l==r)return;
	int mid=l+r>>1;
	pair<ll,int>mn=mp(Inf,0);
	for(int i=l;i<=mid;i++)mn=min(mn,mp(-1LL*i*d+a[i],i));
	for(int i=mid+1;i<=r;i++)e[++tot]=Edge(mn.snd,i,mn.fst+1LL*i*d+a[i]);
	mn=mp(Inf,0);
	for(int i=mid+1;i<=r;i++)mn=min(mn,mp(1LL*i*d+a[i],i));
	for(int i=l;i<=mid;i++)e[++tot]=Edge(i,mn.snd,-1LL*i*d+a[i]+mn.fst);
	solve(l,mid);solve(mid+1,r);
}

int main(){
#ifdef FILE
	freopen("FILE.in","r",stdin);
	freopen("FILE.out","w",stdout);
#endif
	scanf("%d%d",&n,&d);
	REP(i,n)scanf("%d",&a[i]);
	solve(1,n);
	sort(e+1,e+1+tot);
	Dsu::init();
	REP(i,tot){
		int u=Dsu::find(e[i].u),v=Dsu::find(e[i].v);
		if(u==v)continue;
		ans+=e[i].w;
		Dsu::f[u]=v;
	}
	printf("%lld\n",ans);
#ifdef TIME
	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
#endif
	return 0;
}

/*
Input:
-----------------
Output:
*/
