#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const int MAX_N = 1e4 + 10;
ll dp[MAX_N][MAX_N];
ll arr[MAX_N];
ll n, k;

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#endif

    cin >> n >> k;
    for(ll i = 0; i < n; i ++) {
        cin >> arr[i];
    }

    for(int i = 0; i < MAX_N; i ++) {
        for(int j = 0; j < MAX_N; j ++) {
            dp[i][j] = -mod;
        }
    }

    dp[0][0] = 0;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j <= i; j ++) {
            if(j != 0) {
                chkmax(dp[i + 1][j - 1], dp[i][j] + arr[i] - k * (j - 1ll));
            }
            chkmax(dp[i + 1][j], dp[i][j] - k * j);
            chkmax(dp[i + 1][j + 1], dp[i][j] - arr[i] - k * (j + 1ll));
        }
    }

    cout << dp[n][0] << endl;

    return 0;
}
