#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;
a[x-1] = 1e9;
st.push({x-1,x-1});
for(int i = x;i<=n;i++){
while(a[i] >= a[st.top().first])
st.pop();
ndp[i] = dp[st.top().second] + a[st.top().first];
ndp[i] = min(ndp[i],dp[st.top().first] + a[i]);
st.push({i,st.top().first});
}
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
}
