#include <bits/stdc++.h>
#define maxn 100100
using namespace std;
int n, k;
int a[maxn], dp[maxn][110];
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
dp[0][0] = 0;
for(int i = 0; i < n; ++i){
dp[i+1][1] = max(dp[i][1], a[i+1]);
}
for(int j = 2; j <= k; ++j){
vector<pair<int, int> > dpStk;
for(int i = j; i <= n; ++i){
int tmpM = dp[i-1][j-1];
while(!dpStk.empty() and dpStk.back().first <= a[i]){
tmpM = min(tmpM, dpStk.back().second);
dpStk.pop_back();
}
if(dpStk.empty() or dpStk.back().first+dpStk.back().second >= tmpM+a[i]){
dpStk.push_back({a[i], tmpM});
//cerr << tmpM << '\n';
}
dp[i][j] =tmpM+a[i];
if(!dpStk.empty()){
dp[i][j] = min(dpStk.back().first+dpStk.back().second,dp[i][j]);
}
}
}
cout << dp[n][k];
}
