#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+9;
int n,K;
int a[N];
vector<int> st(4*N);
vector<int> dp_before(N),dp_cur(N);
int C(int l,int r);
void compute(int l,int r,int optl,int optr);
void compute1(int l,int r,int optl,int optr);
void build(int id,int l,int r);
int get(int id,int l,int r,int u,int v);
int solve1();
int solve();
signed main(){
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<solve();
//10 5
//9 9 3 5 6 6 2 8 2 2
// srand(time(0));
// int t=10000;
// while(t--){
// n=rand()%10+1;
// K=rand()%n+1;
// for(int i=1;i<=n;i++) a[i]=rand()%10+1;
// int x=solve();
// int y=solve1();
// if(x!=y){
// cout<<n<<' '<<K<<endl;
// for(int i=1;i<=n;i++) cout<<a[i]<<' ';
// cout<<endl;
// cout<<x<<' '<<y<<endl;
// cout<<"WA";
// return 0;
// }
// }
}
int solve(){
build(1,0,n);
for(int i=0;i<=n;i++){
dp_before[i]=C(0,i);
}
for(int i=2;i<=K;i++){
compute(0,n,0,n);
dp_before=dp_cur;
}
return dp_before[n];
}
int solve1(){
vector<vector<int>> dp(n+10,vector<int>(K+10,0));
for(int i=1;i<=n;i++) for(int j=1;j<=K;j++) dp[i][j]=INT_MAX;
for(int i=1;i<=n;i++) dp[i][1]=max(dp[i-1][1],a[i]);
for(int i=1;i<=n;i++){
for(int j=2;j<=i;j++){
int mx=-1;
for(int k=j;k<=i;k++) mx=max(mx,a[k]);
for(int k=2;k<=min(i,K);k++){
dp[i][k]=min(dp[i][k],dp[j-1][k-1]+mx);
}
}
}
return dp[n][K];
}
void build(int id,int l,int r){
if(l==r){
st[id]=a[l];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if(l>v||r<u) return INT_MIN;
if(l>=u&&r<=v) return st[id];
int mid=(r+l)/2;
int get1=get(id*2,l,mid,u,v);
int get2=get(id*2+1,mid+1,r,u,v);
return max(get1,get2);
}
int C(int l,int r){
return get(1,0,n,l,r);
}
void compute(int l,int r,int optl,int optr){
if(l>r) return;
int mid=(l+r)/2;
pair<int,int> best={INT_MAX,-1};
for(int k=1;k<=mid;k++){
if(k>1){
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);
}
