#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int lim=2e5+100;
int mod=1e9+7;
const int inf=INT_MAX;
using pii=pair<int,int>;
struct segtree{
int n;
vector<int>tree;
void init(int N){
n=N;
tree.resize(4*N,inf);
}
int P,VAL;
void update(int l,int r,int node){
if(node==-1&&r==-1)exit(0);
if(l==r){
tree[node]=VAL;
return;
}
int mid=(l+r)>>1,child=node<<1;
if(P<=mid)update(l,mid,child);
else update(mid+1,r,child|1);
tree[node]=min(tree[child],tree[child|1]);
}
void update(int p,int val){
P=p,VAL=val;
update(0,n-1,1);
}
int L,R;
int query(int l,int r,int node){
if(L<=l&&r<=R){
return tree[node];
}
if(r<L||R<l){
return inf;
}
int mid=(l+r)>>1,child=node<<1;
return min(query(l,mid,child),query(mid+1,r,child|1));
}
int query(int l,int r){
L=l,R=r;
return query(0,n-1,1);
}
};
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int dp[k+1][n];
dp[1][0]=a[0];
for(int i=1;i<n;i++){
dp[1][i]=max(dp[1][i-1],a[i]);
}
if(k==1){
cout<<dp[1][n-1];
return 0;
}
int val[k+1][n];
vector<int>stk;
stk.pb(-1);
multiset<int>goodvals[k+1];
for(int i=0;i<=k;i++){
goodvals[i].insert(inf);
}
segtree st[k];
for(int i=0;i<k;i++){
st[i].init(n);
}
for(int i=1;i<n;i++){
st[1].update(i,dp[1][i-1]);
}
for(int i=0;i<n;i++){
while(stk.back()!=-1&&a[stk.back()]<a[i]){
for(int j=2;j<=k;j++){
goodvals[j].erase(goodvals[j].find(val[j][stk.back()]));
}
stk.pop_back();
}
for(int j=2;j<=k;j++){
val[j][i]=st[j-1].query(stk.back()+1,i)+a[i];
goodvals[j].insert(val[j][i]);
}
for(int j=2;j<=k;j++){
dp[j][i]=*goodvals[j].begin();
if(j!=k&&i!=n-1)st[j].update(i+1,dp[j][i]);
}
stk.pb(i);
}
cout<<dp[k][n-1];
}
