RT.

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define gt getchar
#define pt putchar
#define y1 y233
#define int long long
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
const signed N=1e5+5;
using namespace std;
//using namespace __gnu_pbds;
inline bool D(char ch){return ch>='0'&&ch<='9';}
inline int read(){
   	int x=0,f=1;char ch=gt();
   	while(!D(ch)){if(ch=='-')f=-1;ch=gt();}
   	while(D(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;
}
inline void print(int x){
    if(x<0)pt('-'),x=-x;
    if(x>9)print(x/10);
    pt(x%10^48);
}
inline void printsp(int x){
	print(x);
	pt(32);
}
inline void println(int x){
	print(x);
	pt(10);
}
int n,c,maxx,a[1000005],f[N][105],dp[1005][1005],b[N],num;
inline int F(int x,int y){return x>=y?x-y:c;}
signed main(){
	n=read(),c=read();
	if(!c){
		println(0);
		return 0;
	}
	for(int i=1;i<=n;++i){
		a[i]=read();
		b[i]=a[i];
		maxx=max(maxx,a[i]);
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;++i)
		if(a[i]==b[i])num++;
	if(num==n){
		int ans=(n-1)*c;
		for(int i=2;i<=n;++i){
			int cnt=ans+(i-1)*(a[i]-a[i-1])-c;
			ans=min(ans,cnt);
		}
		println(ans);
	}else if(maxx<=100){
		memset(f,0x3f,sizeof(f));
		for(int i=1;i<=100;++i)
			f[0][i]=0;
		for(int i=0;i<=n;++i){
			for(int j=0;j<=100;++j)
				f[i+1][j]=f[i][j]+F(j,a[i+1]);
			for(int j=100;j>=0;--j)
				f[i+1][j]=min(f[i+1][j],f[i+1][j+1]);
		}
		println(f[n][0]);
	}else{
		memset(dp,0x3f,sizeof(dp));
		for(int i=1;i<=n;++i)
			dp[0][i]=0;
		for(int i=0;i<=n;++i){
			for(int j=1;j<=n;++j)
				dp[i+1][j]=dp[i][j]+F(b[j],a[i+1]);
			for(int j=n;j>=1;--j)
				dp[i+1][j]=min(dp[i+1][j],dp[i+1][j+1]);
		}
		println(dp[n][1]);
	}
	return 0;
}