#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5;
const long long maxk = 1e2;
long long a[maxn+1];
long long f[maxn+1][maxk+1];
const long long oo = 1e16;
int main()
{
long long n,k; cin >> n >> k;
for (long long i = 1; i <= n; i++) {cin >> a[i];}
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= k; j++) {f[i][j] = +oo;}
}
/*for (long long i = 1; i <= k; i++)
{
if (i == 1) {f[1][i] = a[1];} else {f[1][i] = +oo;}
}*/
/*for (long long i = 0; i <= k; i++)
{
f[0][i] = +oo;
}
long long totalMax = -1;
for (long long i = 1; i <= n; i++)
{
totalMax = max(totalMax, a[i]);
for (long long j = 1; j <= k; j++)
{
f[i][j] = +oo;
if (j > i) {continue;}
if (j == 1)
{
f[i][j] = totalMax; continue;
}
long long curMax = a[i];
for (long long x = i-1; x >= 1; x--)
{
f[i][j] = min(f[i][j], f[x][j-1] + curMax);
curMax = max(curMax, a[x]);
}
}
}
cout << f[n][k];*/
long long curMax = -1;
for (long long i = 1; i <= n; i++)
{
curMax = max(curMax, a[i]);
f[i][1] = curMax;
}
for (long long i = 2; i <= k; i++)
{
stack<long long> l, s2;
for (long long j = 1; j <= n; j++)
{
long long cur = f[j-1][i-1];
while(!l.empty() && l.top() < a[j])
{
cur = min(cur, s2.top());
l.pop(); s2.pop();
}
if (l.empty() || cur + a[j] < l.top() + s2.top())
{
l.push(a[j]); s2.push(cur);
}
if (j >= i) {f[j][i] = l.top() + s2.top();}
}
}
cout << f[n][k];
}
