#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int K=105;
int n,k;
int a[N],dp[K][N];
struct Info{
int mx,dp_val,pref_mn;
};
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<=n;i++){
dp[1][i]=max(dp[1][i-1],a[i]);
}
for(int j=2;j<=k;j++){
vector<Info> st;
for(int i=j;i<=n;i++){
Info cur{a[i],dp[j-1][i-1],0};
while(!st.empty()&&st.back().mx<cur.mx){
auto e=st.back();
st.pop_back();
cur.dp_val=min(cur.dp_val,e.dp_val);
}
cur.pref_mn=cur.dp_val+cur.mx;
if(!st.empty()){
cur.pref_mn=min(cur.pref_mn,st.back().pref_mn);
}
st.push_back(cur);
dp[j][i]=cur.pref_mn;
}
}
cout << dp[k][n] << "\n";
}
