#include <bits/stdc++.h>
#define N 100005
using namespace std;
int a[N];
int dp[N];
int ndp[N];
void solve(){
int n,k;
cin >> n >> k;
for(int i = 1;i<=n;i++){
cin >> a[i];
dp[i] = 1e9;
}
for(int x = 1;x<=k;x++){
for(int i = 0;i<=n;i++){
ndp[i] = 1e9;
}
stack<pair<int,int>> st;
multiset<int> s;
for(int i = 1;i<=n;i++){
int mini = dp[i-1];
while(st.size() && a[i] >= a[st.top().first]){
mini = min(mini,st.top().second);
s.erase(s.find(a[st.top().first] + st.top().second));
st.pop();
}
st.push({i,mini});
s.insert(a[i] + mini);
assert(a[i] + mini == *s.rbegin());
ndp[i] = *s.begin();
}
for(int i = 0;i<=n;i++){
dp[i] = ndp[i];
//cout << dp[i] << " ";
}
//cout << endl;
}
cout << dp[n];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while(t--){
solve();
}
#ifdef Local
cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
#endif
}
