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

const int mnogo = 1000000007;

int broiDni;
int cenaPrestoi;

int ceniPetrol[1000010];

int priTolova[10010][5010];

int pechalbaPri(int doKade, int sKolkoPetrol){
    if(doKade == 0){
        if(sKolkoPetrol == 0){
            return 0;
        }else{
            return -mnogo;
        }
    }
    if(abs(sKolkoPetrol) > doKade){
        return -mnogo;
    }

    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);

    return tuka;
}

int main(){

    cin>>broiDni>>cenaPrestoi;

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

    int pechalba = pechalbaPri(broiDni, 0);

    cout<<pechalba<<endl;

    return 0;
}
