/**
* author: tourist
* created: 02.07.2025 17:15:02
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
const long long inf = (long long) 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<long long> dp(n + 1, inf), ndp(n + 1, inf);
for (int i = 1; i <= n; i++) {
if (i == 1) {
dp[i] = a[i];
continue;
}
dp[i] = max(dp[i - 1], a[i]);
}
vector<int> l(n + 1, 0);
stack<int> lef;
for (int i = 1; i <= n; i++) {
while (!lef.empty() && a[lef.top()] <= a[i]) {
lef.pop();
}
if (!lef.empty()) {
l[i] = lef.top();
}
lef.push(i);
}
for (int i = 2; i <= k; i++) {
stack<pair<long long, long long>> st;
for (int j = 1; j <= n; j++) {
if (l[j] != 0) {
ndp[j] = ndp[l[j]];
}
long long mn = dp[j - 1];
while (!st.empty() && st.top().second <= a[j]) {
mn = min(mn, st.top().first);
st.pop();
}
ndp[j] = min(ndp[j], mn + a[j]);
st.push({mn, a[j]});
}
for (int j = 0; j <= n; j++) {
dp[j] = ndp[j];
ndp[j] = inf;
}
}
cout << dp[n] << '\n';
return 0;
}
