#include<bits/stdc++.h>
#define el '\n'
using namespace std ;
const int MN = 1e5 + 5;
const int64_t inf = 1e18;
int64_t a[MN];
int32_t main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n , k;
cin >> n >> k;
for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
vector<vector<int64_t>> dp(k + 5 , vector<int64_t>(n + 5 , inf));
dp[1][0] = 0;
for ( int i = 1 ; i <= n ; i++ ) dp[1][i] = max(dp[1][i - 1] , a[i]);
for ( int i = 2 ; i <= k ; i++ ){
stack<pair<int64_t , int>> st;
for ( int j = i ; j <= n ; j++ ){
int64_t cur = dp[i - 1][j - 1];
while (!st.empty() && a[st.top().second] <= a[j]){
cur = min(cur , st.top().first);
st.pop();
}
dp[i][j] = min(dp[i][st.empty() ? 0 : st.top().second] , cur + a[j]);
st.push(make_pair(cur , j));
}
}
cout << dp[k][n];
}
