#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
int N, K;
vector <int> t;
const int maxn = 5000 + 1;
ll dp[maxn][maxn];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
t.resize(N+1);
for (int i = 1; i <= N; i++)
cin >> t[i];
ll ans = 1e18;
for (int i = 0; i <= N; i++) {
fill(dp[i]+1, dp[i] + maxn, 1e18);
}
dp[0][0] = 0;
set <ll> s;
for (int j = 1; j <= K; j++) {
for (int i = 1; i <= N; i++) {
if (i == 1) {
dp[i][j] = 1;
continue;
} else if (j == 1) {
dp[i][j] = t[i] - t[1] + 1;
continue;
} else
s.insert(dp[i-1][j-1] - t[i] + 1);
dp[i][j] = *s.begin() + t[i];
}
s.clear();
}
for (int i = 1; i <= K; i++)
ans = min(ans, dp[N][i]);
cout << ans << '\n';
}
