#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
vector<int> a(n + 1), dp(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
dp[i] = max(dp[i - 1], a[i]);
}
for (int i = 2; i <= k; i++){
vector<int> ndp(n + 1, 1e18);
stack<array<int, 2>> st;
for (int j = i; j <= n; j++){
int cmn = dp[j - 1];
while (!st.empty() && a[st.top()[0]] <= a[j]) {
cmn = min(cmn, st.top()[1]);
st.pop();
}
ndp[j] = cmn + a[j];
if(st.size()) ndp[j] = min(ndp[j], ndp[st.top()[0]]);
st.push({j, cmn});
}
swap(dp, ndp);
}
cout << dp[n];
}
