#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100001];
vector<int> dp_before(1001+1),dp_cur(1001+1);
int C(int l,int r);
void compute(int l,int r,int optl,int optr);
signed main(){
int n,K;
cin>>n>>K;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp_before[i]=C(1,i);
}
for(int i=1;i<=K;i++){
compute(0,n,0,n);
dp_before=dp_cur;
}
cout<<dp_before[n];
}
int C(int l,int r){
int ans=-1;
for(int i=l;i<=r;i++) ans=max(ans,a[i]);
return ans;
}
void compute(int l,int r,int optl,int optr){
if(l>r) return;
int mid=(l+r)>>1;
pair<int,int> best={INT_MAX,-1};
for(int k=optl;k<=min(mid,optr);k++){
best=min(best,{dp_before[k-1]+C(k,mid),k});
}
dp_cur[mid]=best.first;
int opt=best.second;
compute(l,mid-1,optl,opt);
compute(mid+1,r,opt,optr);
}
