#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = std::vector<int>;
using VI2D = std::vector<vector<int>>;
using VLL = std::vector<long long>;
using VLL2D = std::vector<vector<long long>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

constexpr int dx[] = {-1, 0, 1, 0};
constexpr int dy[] = {0, -1, 0, 1};

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int n, k;
	cin >> n >> k;
	VI v(n);
	REP(i, n) { cin >> v[i]; }

	int res_max = 0;
	REP(i, n) { res_max += max(v[i], 0); }
	VI left(k + 1, 0);
	REP(ope, k + 1) {
		REP(bound, ope + 1) {
			int tmp = 0;
			priority_queue<int, VI, greater<int>> pq;
			REP(index, ope) {
				if(index < min(n, bound)) {
					tmp += v[index];
					pq.push(v[index]);
				} else if(!pq.empty() && pq.top() < 0) {
					tmp -= pq.top();
					pq.pop();
				}
			}
			chmax(left[ope], tmp);
		}
	}
	reverse(ALL(v));
	VI right(k + 1, 0);
	REP(ope, k + 1) {
		REP(bound, ope + 1) {
			int tmp = 0;
			priority_queue<int, VI, greater<int>> pq;
			REP(index, ope) {
				if(index < min(n, bound)) {
					tmp += v[index];
					pq.push(v[index]);
				} else if(!pq.empty() && pq.top() < 0) {
					tmp -= pq.top();
					pq.pop();
				}
			}
			chmax(right[ope], tmp);
		}
	}

	int result = 0;
	REP(i, k + 1) { chmax(result, left[i] + right[k - i]); }

	cout << min(result, res_max) << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using P = pair<int, int>;
using E = pair<ll, P>;

const ll INF = 1LL << 60;

int n;
ll D;
ll a[200005];
vector< E > edges;

void solve(int L, int R) {
    if (R - L <= 1) return;
    int mid = (R + L) / 2;

    ll lval = INF;
    int lidx = -1;
    for (int i = L; i < mid; i++) {
        ll tmp = a[i] - D * i;
        if (lval > tmp) {
            lidx = i;
            lval = tmp;
        }
    }

    ll rval = INF;
    int ridx = -1;
    for (int i = mid; i < R; i++) {
        ll tmp = a[i] + D * i;
        if (rval > tmp) {
            ridx = i;
            rval = tmp;
        }
    }

    for (int i = L; i < mid; i++) {
        edges.emplace_back(a[i] + a[ridx] + D * (ridx - i), P(i, ridx));
    }

    for (int i = mid; i < R; i++) {
        edges.emplace_back(a[i] + a[lidx] + D * (i - lidx), P(lidx, i));
    }

    solve(L, mid);
    solve(mid, R);
}

struct UnionFind {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;

    UnionFind(int sz) : data(sz, -1) {}

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }

    int find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return -data[find(x)];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> D;
    for (int i = 0; i < n; i++) cin >> a[i];
    solve(0, n);

    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    ll ans = 0;
    for (E& e : edges) {
        ll cost = e.first;
        int u = e.second.first, v = e.second.second;
        if (!uf.same(u, v)) {
            uf.unite(u, v);
            ans += cost;
        }
    }
    cout << ans << endl;
    return 0;
}