#include <bits/stdc++.h>
using namespace std;
#define int long long int
using pi = pair<int, int>;
const int INF = 4e18;
signed main() { // is this alien trick ??
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
vector<int> times(n);
for (int i = 0; i < n; i++) {
cin >> times[i];
times[i]--;
}
auto g = [&](int la) {
vector<int> DP(n, INF), cnt(n, -INF);
DP[0] = 1+la; cnt[0] = 1;
for (int i = 1; i < n; i++) {
DP[i] = times[i] - times[0] + 1 + la;
cnt[i] = 1;
for (int j = 1; j <= i; j++) {
int cand = DP[j-1] + (times[i] - times[j] + 1 + la);
if (cand < DP[i] || cand == DP[i] && cnt[j-1] + 1 > cnt[i]) {
DP[i] = cand;
cnt[i] = cnt[j-1]+1;
}
}
}
// cout << "λ = " << la << " DP = " ; for (auto &el : DP) cout << el << " "; cout << "\n";
// cout << "DP[n-1] = " << DP[n-1] << " cnt[n-1] = " << cnt[n-1] << "\n";
return make_pair(DP[n-1], cnt[n-1]);
};
int lo = 0, hi = 1e18;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
pi fx = g(mid);
if (fx.second > k) {
lo = mid + 1;
} else {
hi = mid;
}
}
pi r1 = g(lo), r2 = g(lo-1);
cout << max(r1.first - k * lo, r2.first - k * (lo-1)) << "\n";
// DP[k][i] = minimum cost to cover everything up to person i, using exactly k segments
// DP[1][i] = times[i] - times[0] + 1
// DP[k>1][i] = min(DP[k-1][i], DP[k-1][j] + times[i] - times[j+1] + 1) for j < i
// vector<vector<int>> DP(k+1, vector<int>(n, INF));
// vector<vector<int>> prefix_min(k+1, vector<int>(n+1, INF));
// for (int i = 0; i < n; i++) {
// DP[1][i] = times[i] - times[0] + 1;
// if (i < n - 1) prefix_min[1][i+1] = min(prefix_min[1][i], DP[1][i] - times[i+1] + 1);
// }
// for (int s = 2; s <= k; s++) {
// DP[s][0] = DP[1][0];
// prefix_min[s][1] = min(prefix_min[s][0], DP[s][0] - times[1] + 1);
// for (int i = 1; i < n; i++) {
// DP[s][i] = min(DP[s-1][i], prefix_min[s-1][i] + times[i]);
// if (i < n - 1) prefix_min[s][i+1] = min(prefix_min[s][i], DP[s][i] - times[i+1] + 1);
// }
// }
// cout << DP[k][n-1] << "\n";
return 0;
}
