#include<bits/stdc++.h>
using namespace std;
int n, k, dp[3][100002], v[100002];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> v[i];
int mx = 0;
for(int i = 1; i <= n; ++i)
{
mx = max(mx, v[i]);
dp[1][i] = mx;
}
for(int i = 2; i <= k; ++i)
{
deque<int>val;
deque<int>pmax;
deque<int>pmin;
for(int j = i; j <= n; ++j)
{
int zmin = j-1;
while(!val.empty() && v[j] >= v[val.back()])
{
if(dp[1][pmin.back()] < dp[1][zmin])
zmin = pmin.back();
pmin.pop_back();
val.pop_back();
pmax.pop_back();
}
val.push_back(j);
pmin.push_back(zmin);
if(val.size() == 1)
pmax.push_back(dp[1][zmin] + v[j]);
else
{
if(pmax.back() < dp[1][zmin] + v[j])
pmax.push_back(pmax.back());
else
pmax.push_back(dp[1][zmin] + v[j]);
}
dp[2][j] = pmax.back();
}
for(int j = 1; j <= n; ++j)
dp[1][j] = dp[2][j], dp[2][j] = 0;
}
cout << dp[1][n] << '\n';
return 0;
}
