/*
IZhO 14-Blocks(same as this 2008 Romanian problem - https://www.infoarena.ro/problema/ksecv)
We can solve it using deques, where dp[i][j] = min sum if we split the first j numbers in i sequences
*/
#include<bits/stdc++.h>
using namespace std;
int n, k, dp[3][100002], v[100002];
int val[100002], pmax[100002], pmin[100002], sz;
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)
{
sz = 0;
for(int j = i; j <= n; ++j)
{
int zmin = j-1;
while(sz && v[j] >= v[val[sz]])
{
if(dp[1][pmin[sz]] < dp[1][zmin])
zmin = pmin[sz];
--sz;
}
++sz;
val[sz] = j;
pmin[sz] = zmin;
if(sz == 1)
pmax[sz] = dp[1][zmin] + v[j];
else
{
if(pmax[sz - 1] < dp[1][zmin] + v[j])
pmax[sz] = pmax[sz - 1];
else
pmax[sz] = dp[1][zmin] + v[j];
}
dp[2][j] = pmax[sz];
}
for(int j = 1; j <= n; ++j)
dp[1][j] = dp[2][j], dp[2][j] = 0;
}
cout << dp[1][n] << '\n';
return 0;
}
