#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ft first
#define sd second
const ll MOD = 1e9+7;
ll n, k, arr[100005], dp[100005][101];
void fun(){
memset(arr, 0x3f, sizeof(arr));
cin>>n>>k;
for(int i = 1; i <= n; i++)cin>>arr[i];
for(int i = 1; i <= n; i++)dp[i][1] = max(arr[i], dp[i - 1][1]);
for(int j = 2; j <= k; j++){
stack<pair<ll, ll> >st;
for(int i = j; i <= n - (k - j); i++){
ll x = dp[i - 1][j - 1];
while(!st.empty() && arr[st.top().ft] <= arr[i]){
x = min(x, st.top().sd);
st.pop();
}
dp[i][j] = min(x + arr[i], (!st.empty() ? dp[st.top().ft][j] : (ll)2e18));
st.push({i, x});
}
}
cout<<dp[n][k];
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int ttt = 1;
//cin>>ttt;
while(ttt--)fun();
}
