#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;
vector<int> dp_before,dp_cur;
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);
int solve1();
signed main(){
cin>>n>>K;
for(int i=1;i<=n;i++) cin>>a[i];
if(n<=100){
cout<<solve1();
}
else{
st.reserve(4*n+10);
dp_before.reserve(n+10);
dp_cur.reserve(n+10);
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];
}
}
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_MAX;
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=optl;k<=min(mid,optr);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);
}
