#include <bits/stdc++.h>
using namespace std;
int const MAX=1e5+5;
long long dp[MAX];
long long old_dp[MAX];
int n,k;
int v[MAX];
void read(){
cin>>n>>k;
int i;
for(i=1;i<=n;++i)
cin>>v[i];
}
void minself(long long& x,long long val){
if(x>val)
x=val;
}
struct structy{
int val;
long long old,dp;
};
void upgrade(){
int i;
for(i=0;i<=n;++i)
old_dp[i]=dp[i];
stack<structy>stv;
for(i=1;i<=n;++i){
long long old=old_dp[i-1];
while(!stv.empty() && stv.top().val<=v[i]){
minself(old,stv.top().old);
stv.pop();
}
dp[i]=old+v[i];
if(!stv.empty())
minself(dp[i],stv.top().dp);
stv.push({v[i],old,dp[i]});
}
}
int solve(){
dp[0]=1e18;
dp[1]=v[1];
int i;
for(i=2;i<=n;++i)
dp[i]=max((int)dp[i-1],v[i]);
for(i=2;i<=k;++i)
upgrade();
return dp[n];
}
int main()
{
read();
cout<<solve();
return 0;
}
