//#pragma GCC optimize("O3, Ofast, unroll-loops, inline, no-stack-protector")
#include <bits/stdc++.h>
//#pragma GCC target("avx2")

using namespace std;

using ll = long long;
using pii = pair<int, int>;

ll ans = 0;

int k;

void gen(ll res, vector<int> &a, int count) {
    if (a.empty() && count == k) {
        ans = max(ans, res);
        return;
    }
    if (count >= k) return;
    int n = (int) a.size();
    for (int mask = 1; mask < (1 << n); ++mask) {
        vector<int> b;
        int now = 0;
        int cnt = 1;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                now = max(a[i] + cnt, now);
                ++cnt;
            } else {
                b.push_back(a[i]);
            }
        }
        gen(res + now, b, count + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    const ll inf = 1e18;
    vector<ll> dp(k + 1, -inf);
    vector<int> pred(k + 1, -1);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = k; j > 0; --j) {
            if (dp[j - 1] == -inf) continue;
            if (dp[j - 1] + a[i] + i - pred[j - 1] > dp[j]) {
                dp[j] = dp[j - 1] + a[i] + i - pred[j - 1];
                pred[j] = i;
            }
        }
    }
    cout << dp[k];
}
