#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int N = 100005;
const int K = 103;
const int inf=1e9;
int dp[N], ndp[N], pos[N], lg[N];
int sp[N][17];
int get(int l, int r){
if(l>r)return 0;
int rng=r-l+1;
int lga=lg[rng];
return max(sp[l][lga], sp[r-(1<<lga)+1][lga]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int a[n];
for(int i=0; i< n; i++)cin >> a[i];
int mx=0;
lg[1]=0;
for(int i=2; i<N; i++){
lg[i]=lg[i/2]+1;
}
for(int i=0; i< n; i++){
mx=max(mx, a[i]);
dp[i]=mx;
sp[i][0]=a[i];
}
for(int j=1; j<17; j++){
for(int i=0; i+(1<<j)<=n; i++){
sp[i][j]=max(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
}
}
stack<pair<int, int>> st;
st.push({inf, -1});
for(int i=0; i< n; i++){
while(!st.empty() && st.top().F<=a[i]){
st.pop();
}
pos[i]=st.top().S+1;
st.push({a[i], i});
}
while(!st.empty())st.pop();
for(int j=2; j<=k; j++){
st.push({inf, -1});
for(int i=0; i< n; i++){
int ps=pos[i];
pair<int, int> lst={-2, -1};
while(ps<=st.top().S){
lst=st.top();
st.pop();
if(st.size()==0)break;
}
if(st.size()==0)st.push(lst);
else if(lst.F!=-2 && st.top().F+get(st.top().S+1, i)>lst.F+get(lst.S+1, i))st.push(lst);
ndp[i]=st.top().F+get(st.top().S+1, i);
while(!st.empty() && st.top().F>= dp[i])st.pop();
if(dp[i]<ndp[i])st.push({dp[i], i});
}
while(!st.empty())st.pop();
for(int i=0; i< n; i++){
dp[i]=ndp[i];
}
}
cout << dp[n-1] << '\n';
}
