#include <bits/stdc++.h>
using namespace std;
const int oo = 1000111000;
int n, k;
int a[100005];
int f[105][100005];
void SubEnd() {
for (int i = 2; i <= k; ++i) {
stack<pair<int, int> > S;
for (int j = i; j <= n; ++j) {
int minF = f[i - 1][j - 1];
while (!S.empty() && a[S.top().second] <= a[j]) {
minF = min(minF, S.top().first);
S.pop();
}
f[i][j] = min(f[i][S.empty() ? 0 : S.top().second], minF + a[j]);
S.push(make_pair(minF, j));
}
}
cout<<f[k][n];
}
int32_t main()
{
cin >> n >> k;
memset(f, 0x3f, sizeof f);
f[1][0]=0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
//f[0][i]=0;
}
for (int i=1;i<=n;i++) f[1][i]=max(f[1][i-1],a[i]);
SubEnd();
}
