#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int K = 105;
int dp[N][K],choice[N][K];
int main() {
int n,k;
cin>>n>>k;
vector<int>v(n+1);
for(int i = 1;i<=n;i++)cin>>v[i];
for(int i = 1;i<=n;i++) {
dp[i][1] = max(dp[i-1][1],v[i]), choice[i][1] = dp[i][1];
}
for(int j = 2;j<=k;j++) {
stack<int> s;
for(int i = j;i<=n;i++) {
dp[i][j] = dp[i-1][j-1] + v[i]; // single group
choice[i][j] = v[i];
while(!s.empty() && v[s.top()] <= v[i]) {
int idx = s.top();
if(dp[idx][j] - choice[idx][j] + max(choice[idx][j],v[i]) < dp[i][j]) {
dp[i][j] =dp[idx][j] - choice[idx][j] + max(choice[idx][j],v[i]);
// if(choice[idx][j]>choice[i][j])choice[i][j] = choice[idx][j];
}
s.pop();
}
if(!s.empty()) {
int idx = s.top();
if(dp[idx][j] < dp[i][j]){
dp[i][j] = dp[idx][j];
choice[i][j] = choice[idx][j];
}
}
s.push(i);
}
}
// for(int i = 1;i<=n;i++) {
// for(int j = 1;j<=k;j++) cout << dp[i][j] << " ";
// cout << "\n";
// }
cout<<dp[n][k];
}
