#include <bits/stdc++.h>
using namespace std;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("blocks.in", "r", stdin);
// freopen("blocks.out", "w", stdout);
int n, k; cin >> n >> k;
vector<int> x(n);
for(int i = 0; i < n; i++){
cin >> x[i];
}
x.push_back(-1e9);
vector<int> r(n+1, n);
stack<int> g;
for(int i = n-1; i >= 0; i--){
while(g.size() > 0){
if(x[g.top()] <= x[i]){
g.pop();
}else{
break;
}
}
if(g.size() > 0){
r[i] = g.top();
}
g.push(i);
}
vector<vector<int>> dp(n+1, vector<int>(k+5, 1e9));
vector<priority_queue<pair<int, int>>> s(k+5);
dp[0][1] = 0;
for(int i = 0; i <= n; i++){
for(int y = k+1; y >= 1; y--){
while(s[y].size() > 0){
if(s[y].top().second < i){
s[y].pop();
}else{
break;
}
}
if(s[y].size() > 0){
dp[i][y] = min(-s[y].top().first, dp[i][y]);
}
if(i == n) continue;
if(r[i] != n){
dp[r[i]][y] = min(dp[r[i]][y], dp[i][y]);
}
s[y+1].push({-(dp[i][y] + x[i]), r[i]});
}
}
cout << dp[n][k+1] << "\n";
return 0;
}
