#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

const int mod = 10;

struct Modular {
    int x;

    Modular(int x = 0): x(x) {}

    friend Modular operator+(Modular a, Modular b) {
        int res = a.x + b.x;
        return res - (res >= mod ? mod : 0);
    }

    friend Modular operator-(Modular a, Modular b) {
        int res = a.x - b.x;
        return res + (res < 0 ? mod : 0);
    }

    friend Modular operator*(Modular a, Modular b) {
        return ll(a.x) * b.x % mod;
    }
};

const int maxn = 5e5;
ll a[maxn];
ll dp[maxn + 1];
ll cnt[maxn + 1];
int n;

pair<ll, ll> calc(ll L) {
    cnt[0] = 0;
    dp[0] = 0;
    for(int i = 1; i <= n; ++i){
        dp[i] = 0;
        cnt[i] = 0;
        ll mx = a[i - 1];
        for(int j = i - 1; j >= 0; --j){
            if (dp[i] < dp[j] + mx + L - j || (dp[i] < dp[j] + mx + L - j && cnt[i] > cnt[j] + 1)) {
                dp[i] = dp[j] + mx + L - j;
                cnt[i] = cnt[j] + 1;
            }
            mx = max(mx, a[j - 1]);
        }
    }
    return {dp[n], cnt[n]};
}

void solve() {
    int k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] += i + 1;
    }
    ll l = -1e15;
    ll r = 1e15;
    while (r - l > 1) {
        ll mid = (l + r) / 2;
        auto res = calc(mid);
        if (res.second < k) {
            l = mid;
        } else {
            r = mid;
        }
    }
    auto ans = calc(r);
    cout << ans.first - r * k;
}

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("C:\\Users\\User\\aboab\\input.txt", "r", stdin);
#endif
    solve();
}