#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
const int inf = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
vector<int> a(n + 1, inf);
for (int i = 1; i <= n; i++)
cin >> a[i];
vector<vi> dp(k + 1, vi(n + 1, inf));
dp[0][0] = 0;
for (int j = 1; j <= k; j++) {
stack<ii> stk;
for (int i = j; i <= n; i++) {
int minF = dp[j - 1][i - 1];
while (!stk.empty() && a[stk.top().st] < a[i]) {
minF = min(minF, stk.top().nd);
stk.pop();
}
dp[j][i] = minF + a[i];
if (!stk.empty()) dp[j][i] = min(dp[j][i], dp[j][stk.top().st]);
stk.push({i, minF});
}
}
cout << dp[k][n];
return 0;
}
