#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll dp[2][N],a[N];
int main(){
int n,k; cin>>n >>k;
for(int i=1;i<=n;i++) cin>>a[i];
dp[0][0]=0;
for(int i=1;i<=n;i++) dp[0][i]=LLONG_MAX;
for(int i=1;i<=k;i++){
int now=i&1;
int pre=(i+1)&1;
stack<tuple<int,ll,ll>> st;
//index,minimum value in stack,minimum of the range
for(int j=0;j<=n;j++) dp[now][j]=LLONG_MAX;
for(int j=1;j<=n;j++){
ll mn=dp[pre][j-1];
while(!st.empty() && a[get<0>(st.top())]<=a[j]){
auto [idx,cal,pt]=st.top();
st.pop();
mn=min(mn,pt);
}
ll cd=(mn==LLONG_MAX)?LLONG_MAX:mn+a[j];
// if(st.empty()) cout<<"-1\n";
// else cout<<get<0>(st.top()) <<" " <<get<1>(st.top()) <<" " <<get<2>(st.top()) <<"\n";
if(!st.empty()) st.push({j,min(get<1>(st.top()),cd),mn});
else st.push({j,cd,mn});
dp[now][j]=get<1>(st.top());
//cout<<dp[now][j] <<" ";
}
//cout<<"\n";
}
cout<<dp[k&1][n];
}
