#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>;
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);
}
for(int i=0;i<n;i++){
for(int j=2;j<=k;j++){
if(i)val[j][i]=dp[j-1][i-1];
else val[j][i]=inf;
}
while(stk.back()!=-1&&a[stk.back()]<a[i]){
for(int j=2;j<=k;j++){
if(val[j][stk.back()]!=inf){
val[j][i]=min(val[j][i],val[j][stk.back()]-a[stk.back()]);
goodvals[j].erase(goodvals[j].find(val[j][stk.back()]));
}
}
stk.pop_back();
}
for(int j=2;j<=k;j++){
if(val[j][i]!=inf){
val[j][i]+=a[i];
goodvals[j].insert(val[j][i]);
}
}
for(int j=2;j<=k;j++){
dp[j][i]=*goodvals[j].begin();
}
stk.pb(i);
}
cout<<dp[k][n-1];
}
