#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
const int N = 1e5 + 5;
const int K = 105;
template <typename T>
struct SegmentTree {
vector <T> f;
T NEUTRAL = numeric_limits <T>::max();
int n;
SegmentTree(int _n) { init(_n); }
void init(int _n) {
n = _n;
f.resize((_n << 1) + 5, NEUTRAL);
}
T merge(T x, T y) { return min(x, y); }
void upd(int x, T val) {
x += n;
f[x] = merge(f[x], val);
for (; x > 0; x >>= 1)
f[x >> 1] = merge(f[x], f[x ^ 1]);
}
T qry(int l, int r) {
T ql = NEUTRAL;
T qr = NEUTRAL;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ql = merge(ql, f[l++]);
if (r & 1) qr = merge(f[--r], qr);
}
return merge(ql, qr);
}
};
int n, k;
int a[N], lhs[N];
ll dp[K][N];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
// dp(k, i) = min(dp(k - 1, j) + max(j..i));
// j = lhs[i] + 1; -> dp(k, i) = a[i] + min(dp(k - 1, j)) (j : lhs[i] + 1 -> i);
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;
for (int i = 1; i <= n; ++i)
dp[1][i] = max(dp[1][i - 1], 1LL * a[i]);
for (int _k = 2; _k <= k; ++_k) {
stack <pair <ll, int>> S;
for (int i = _k; i <= n; ++i) {
ll p = dp[_k - 1][i - 1];
while (!S.empty() && a[i] >= a[S.top().second]) {
p = min(p, S.top().first);
S.pop();
}
int j = S.empty()? 0 : S.top().second;
dp[_k][i] = min(dp[_k][j], p + a[i]);
S.push({p, i});
}
}
cout << dp[k][n] << "\n";
}
