#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1000005;
int money[maxn][2]; ///money[q][i] - макс. пари при количество петрол q в края на i-тата седмица
                    ///в задачата не използваме i, а i%2, за да не пазим ненужна информация
int price[maxn];    ///price[i] - цената на петрола за i-тата седмица

int Max (int a, int b, int c){  ///да не повярва човек... 10 мин се чудя защо ми дава там една грешка, а то съм забравил, че вградената max() има само два аргумента; nvm, дефинираме си своя Max()
    return max(max(a, b), c);
}

int main(){

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

    int n, s;
    cin >> n >> s;

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

    ///база за i = 1
    money[0][1] = 0;
    money[1][1] = - price[1] - s * 1;
    //cout << "money [ 0 ][ 1 ] = 0" << endl;
    //cout << "money [ 1 ][ 1 ] = " << money[1][1] << endl;

    for(int i=2; i<=n; i++){        ///i - номер на седмица

        int curr = i%2;             ///номер на сегашната седмица (като остатък при делние на 2)
        int prev = 1 - i%2;         ///номер на предишната седмица (като остатък при делние на 2)

        int q = 0;                  ///q - количество петрол; проверка при q = 0
        money[q][curr] = max(money[q][prev], money[q+1][prev] + price[i]);
        //cout << "money [ " << q << " ][ " << i << " ] = " << money[q][curr] << endl;

        for(q=1; q<=i && q<=n-i; q++){    ///проверка за останалите възможни стойности на q (за i-тата седмица то е най-много i, защото започаме с 0, и също най-много N-i, защото в края имаме 0)

            if(q+1 <= i-1 && q+1 <= n - (i-1)){
                money[q][curr] = Max(money[q-1][prev] - price[i], money[q][prev], money[q+1][prev] + price[i]);
                //if(i == 2 && q==1) cout << "--------- 1" << endl;
            }
            else if(q <= i-1 && q <= n - (i-1)){
                money[q][curr] = max(money[q-1][prev] - price[i], money[q][prev]);
                //if(i == 2 && q==1) cout << "--------- 2" << endl;
            }
            else{
                money[q][curr] = money[q-1][prev] - price[i];
                //if(i == 2 && q==1) cout << "--------- 3" << endl;
            }

            money[q][curr] -= s * q;
            //cout << "money [ " << q << " ][ " << i << " ] = " << money[q][curr] << endl;
        }
    }

    cout << money[0][n%2] << endl;

    return 0;
}
