#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 build(int id,int l,int r);
int get(int id,int l,int r,int u,int v);
signed main(){
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i];
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;
}
cout<<dp_before[n];
}
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 -1e18;
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={1e18,-1};
for(int k=mid;k>=optl;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);
}
