#include <bits/stdc++.h>
using namespace std;
int n,k,arr[100001],dp[101][100001];
int main(){
cin >> n >> k;
for(int i = 0 ; i <= k ; i += 1){
for(int j = 0 ; j <= n ; j += 1){
dp[i][j] = 1000000000;
}
}
int mx = 0;
for(int i = 1 ; i <= n ; i += 1){
cin >> arr[i];
mx = max(mx,arr[i]);
dp[1][i] = mx;
}
for(int i = 2 ; i <= k ; i += 1){
stack<int> st1,st2;
for(int j = 1 ; j <= n ; j += 1){
int best = dp[i-1][j-1];
while(st1.size() && st1.top() < arr[j]){
best = min(best,st2.top());
st1.pop(),st2.pop();
}
if(!st1.size() || best+arr[j] < st1.top()+st2.top()){
st1.push(arr[j]),st2.push(best);
}
if(j >= i){
dp[i][j] = st1.top()+st2.top();
// cout << i << " " << j << " " << dp[i][j] << " " << st1.top() << " " << st2.top() << endl;
}
}
}
cout << dp[k][n] << endl;
}
