#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,a[100005]={0},f[105][100005]={0};
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("BLOCKS.INP","r",stdin);
//freopen("BLOCKS.OUT","w",stdout);
cin >> n>> k;
for (ll i=1;i<=n;i++) cin >> a[i];
for (ll i=1;i<=n;i++)
{
f[1][i]=max(f[1][i-1],a[i]);
}
for (ll i=2;i<=n;i++)
{
stack <pair <ll,ll>> q;
for (ll j=i;j<=n;j++)
{
ll t=f[i-1][j-1];
while (!q.empty() && q.top().first <a[j])
{
t=min(t,q.top().second);
q.pop();
}
if (q.empty() || q.top().first + q.top().second > t +a[j])
{
q.push(make_pair(a[j],t));
}
f[i][j]=q.top().first + q.top().second;
}
}
cout << f[k][n];
return 0;
}
