#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;

const int mnogo = 1000000007;
const int petrol = 350;

int broiDni;
int cenaPrestoi;

int ceniPetrol[1000010];

int priTolova[2048][2048];

int pechalbaPri(int doKade, int sKolkoPetrol){
    if(doKade == 0){
        if(sKolkoPetrol == 0){
            return 0;
        }else{
            return -mnogo;
        }
    }
    if(priTolova[doKade][sKolkoPetrol + petrol] > -mnogo){
        return priTolova[doKade][sKolkoPetrol + petrol];
    }

    int akoNePipame = pechalbaPri(doKade - 1, sKolkoPetrol);

    int akoKupim = pechalbaPri(doKade - 1, sKolkoPetrol + 1) - ceniPetrol[doKade];

    int akoProdadem = pechalbaPri(doKade - 1, sKolkoPetrol - 1) + ceniPetrol[doKade];

    int tuka = max(akoNePipame, max(akoKupim, akoProdadem)) - cenaPrestoi*abs(sKolkoPetrol);

    priTolova[doKade][sKolkoPetrol + petrol] = tuka;
    return tuka;
}

int sCycli(int zaDoKade, int zaKolkoPetrol){
    for(int i = 0; i <= petrol*2; i++){
        priTolova[0][i] = -mnogo;
    }
    priTolova[0][petrol] = 0;

    for(int doKade = 1; doKade <= zaDoKade; doKade++){
        for(int sKolkoPetrol = -broiDni; sKolkoPetrol <= broiDni; sKolkoPetrol++){
            int akoNePipame = priTolova[doKade - 1][sKolkoPetrol + petrol];

            int akoKupim = priTolova[doKade - 1][sKolkoPetrol + 1 + petrol] - ceniPetrol[doKade];

            int akoProdadem = priTolova[doKade - 1][sKolkoPetrol - 1 + petrol] + ceniPetrol[doKade];

            int tuka = max(akoNePipame, max(akoKupim, akoProdadem)) - cenaPrestoi*abs(sKolkoPetrol);

            priTolova[doKade][sKolkoPetrol + petrol] = tuka;
        }
    }

    return priTolova[zaDoKade][zaKolkoPetrol + petrol];
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>broiDni>>cenaPrestoi;

    for(int i = 1; i <= broiDni; i++){
        cin>>ceniPetrol[i];
    }

    int pechalba = sCycli(broiDni, 0);

    cout<<pechalba<<endl;

    return 0;
}
