#include <iostream>
#include <random>
#include <cmath>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <vector>
#include <string>


#define all(x) x.begin(), x.end()
#define ll long long
#define vll vector<ll>
#define MAXN 501'000
#define LOGMAX 21


using namespace std;

vll suff_max, a, ai;
ll n, k, ans = 0;

ll sp[LOGMAX][MAXN];
ll lg[MAXN];

ll rmq(ll ql, ll qr) { // [)
    ll t = lg[qr - ql];

    return max(sp[t][ql], sp[t][qr - (1LL << t)]);
}


void recurs(ll i, vector<pair<ll, ll>> &curr) {
    if (i == n) {
        ll summ = 0;
        for (ll j = 0; j < curr.size(); j++) {
            if (curr[j].second == 0) return;
            summ += curr[j].first;
        }
        ans = max(ans, summ);
        return;
    }

    for (ll j = 0; j < k; j++) {
        pair<ll, ll> oldval = curr[j];
        curr[j].first = max(curr[j].first, a[i] + curr[j].second + 1);
        curr[j].second += 1;
        recurs(i + 1, curr);
        curr[j] = oldval;
    }
}

signed main() {
    // ll n, k;
    // cin >> n;
    cin >> n >> k;

    a.resize(n, 0);
    ai.resize(n, 0);
    suff_max.resize(n, 0);

    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        ai[i] = a[i] + i + 1;
    }

    lg[1] = 0;
    for (ll j = 1; j <= LOGMAX; j++) {
        if ((1LL << j) > n) break;
        lg[(1LL << j)] = j;
        for (ll i = (1LL << (j - 1)) + 1; i < (1LL << j); i++) {
            if (i >= MAXN) break;
            lg[i] = j - 1;
        }
    }

    for (ll i = 0; i < n; i++) {
        sp[0][i] = ai[i];
    }
    for (ll j = 1; j < LOGMAX; j++) {
        for (ll i = 0; i + (1LL << (j - 1)) < n; i++) {
            // if (i + (1LL << j) >= MAXN) break;
            sp[j][i] = max(sp[j - 1][i], sp[j - 1][i + (1LL << (j - 1))]);
        }
    }

    vector<pair<ll, ll>> curr(k, {0, 0});
    //recurs(0, curr);

    /*for (ll i = 0; i < n; i++) {
        if (k == 0) break;
        ans += a[i] + 1;
        k--;
    }*/

    vector<vector<ll>> dp(n, vector<ll> (k + 1, 0));
    vector<ll> pref_max(k + 1, 0);
    ll globalmax = a[0] + 1;
    for (ll i = 0; i < n; i++) {
        globalmax = max(globalmax, a[i] + i + 1);
        dp[i][1] = globalmax;
        // pref_max[1] = max(pref_max[1], dp[i][1] + )
        /*for (ll j = 0; j <= min(i + 1, k) - 1; j++) {
            pref_max[j].first = max(pref_max[j].first, cons_max[j] + a[i] + i - pref_max[j].second);
        }*/
        /*if (dp[i][1] > dp[pref_max[1]][1]) {
            pref_max[1] = i;
        }*/
        // pref_max[1] = max(pref_max[1], dp[i][1]);
        for (ll j = 1; j <= min(i + 1, k); j++) {
            for (ll k = i - 1; k >= 0; k--) {
                ll maximum = rmq(k + 1, i + 1) - k - 1;
                // for (ll u = k + 1; u <= i; u++) maximum = max(maximum, a[u] + u - k);
                dp[i][j] = max(dp[i][j], dp[k][j - 1] + maximum);
            }

            /*ll left = -1, right = i;
            while (right - left > 2) {
                ll lm = left + (right - left) / 3;
                ll rm = right - (right - left) / 3;

                ll maximum = a[i], lval = 0, rval = 0;
                //maximum = rmq(lm + 1, i + 1) - lm - 1;
                for (ll u = lm + 1; u <= i; u++) {
                    maximum = max(maximum, a[u] + u - lm);
                }
                lval = dp[lm][j - 1] + maximum;

                maximum = a[i];
                for (ll u = rm + 1; u <= i; u++) {
                    maximum = max(maximum, a[u] + u - rm);
                }
                //maximum = rmq(rm + 1, i + 1) - rm - 1;
                rval = dp[rm][j - 1] + maximum;

                if (lval < rval) {
                    left = lm;
                } else {
                    right = rm;
                }
            }

            ll k = (left + right) / 2;
            if (k < i) {
                //ll maximum = rmq(k + 1, i + 1) - k - 1;
                ll maximum = 0;
                for (ll u = k + 1; u <= i; u++) maximum = max(maximum, a[u] + u - k);
                dp[i][j] = max(dp[i][j], dp[k][j - 1] + maximum);
            }*/   
        }
    }

    for (ll i = n - 1; i >= 0; i--) {
        ans = max(ans, dp[i][k]);
    }

    cout << ans << endl;
    // cout << n << endl;
}