#include <iostream>
#define ll long long
#define endl "\n"
using namespace std;

const ll maxn = 1e6+2,inf=-1e8;
ll seg[maxn],pred[maxn],n,s,p[maxn];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
    cin >> n >> s;
    for(ll i=0;i<n;i++){
        cin >> p[i];
    }
    for(ll i=2;i<n;i++){
        pred[i]=inf;
    }
    pred[0]=0;
    pred[1]=-p[0]-s;
    for(ll i=1;i<n;i++){
        for(ll k=0;k<n/2+2;k++){
            if(k>i+2){
                seg[k]=inf;
                break;
            }
            if(i+k>n/2+4){
                seg[k]=inf;
                break;
            }
            if(k==0){
                seg[k]=max(pred[k],pred[k+1]+p[i])-k*s;
                continue;
            }
            if(k==n-1){
                seg[k]=max(pred[k],pred[k-1]-p[i])-k*s;
                continue;
            }
            seg[k]=max(max(pred[k],pred[k-1]-p[i]),pred[k+1]+p[i])-k*s;
        }
        for(ll k=0;k<n;k++){
            pred[k]=seg[k];
            //cout << seg[k] << " ";
        }
        //cout << endl;
    }
    cout << seg[0] << endl;
return 0;
}
/*
#include <iostream>
#define ll long long
#define endl "\n"
using namespace std;

const ll maxn = 1e4,inf=-1e8;
ll din[maxn][maxn],n,s,p[maxn];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
    cin >> n >> s;
    for(ll i=0;i<n;i++){
        cin >> p[i];
    }
    for(ll i=0;i<n;i++){
        for(ll k=0;k<n;k++){
            din[i][k]=inf;
        }
    }
    din[0][0]=0;
    din[0][1]=-p[0]-s;
    for(ll i=1;i<n;i++){
        for(ll k=0;k<n;k++){
            if(k>i+1){
                din[i][k]=inf;
            }
            if(k==0){
                din[i][k]=max(din[i-1][k],din[i-1][k+1]+p[i])-k*s;
                continue;
            }
            if(k==n-1){
                din[i][k]=max(din[i-1][k],din[i-1][k-1]-p[i])-k*s;
                continue;
            }
            din[i][k]=max(max(din[i-1][k],din[i-1][k-1]-p[i]),din[i-1][k+1]+p[i])-k*s;
        }
    }
    for(ll i=0;i<n;i++){
        for(ll k=0;k<n;k++){
            cout << din[i][k] << " ";
        }
        cout << endl;
    }
    cout << din[n-1][0] << endl;
return 0;
}
*/
