#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
// Bottom-up segment tree supporting range-add and range-min
struct SegTree {
int n;
vector<ll> tree, lazy;
SegTree(int _n) : n(_n), tree(2*n, INF), lazy(n, 0) {}
// build from base array of size n+1 (0..n)
void build(const vector<ll>& base) {
for (int i = 0; i <= n; i++) tree[i + n] = base[i];
for (int i = n - 1; i >= 1; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
// apply at position p
void apply(int p, ll v) {
tree[p] += v;
if (p < n) lazy[p] += v;
}
// push from p
void push(int p) {
int h = __builtin_ctz(p);
for (int s = h; s > 0; s--) {
int i = p >> s;
if (lazy[i]) {
apply(i<<1, lazy[i]);
apply(i<<1|1, lazy[i]);
lazy[i] = 0;
}
}
}
// pull at p
void pull(int p) {
while (p > 1) {
p >>= 1;
tree[p] = min(tree[p<<1], tree[p<<1|1]) + lazy[p];
}
}
// range add [l, r]
void range_add(int l, int r, ll v) {
l += n; r += n;
int l0 = l, r0 = r;
for (; l <= r; l >>= 1, r >>= 1) {
if (l&1) apply(l++, v);
if (!(r&1)) apply(r--, v);
}
pull(l0);
pull(r0);
}
ll range_min(int l, int r) {
l += n; r += n;
push(l); push(r);
ll res = INF;
for (; l <= r; l >>= 1, r >>= 1) {
if (l&1) res = min(res, tree[l++]);
if (!(r&1)) res = min(res, tree[r--]);
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, K;
cin >> n >> K;
vector<ll> a(n+1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<ll> dp_prev(n+1, INF), dp_cur(n+1, INF);
dp_prev[0] = 0;
// base k=1
for (int i = 1; i <= n; i++) dp_prev[i] = max(dp_prev[i-1], a[i]);
SegTree st(n+1);
for (int k = 2; k <= K; k++) {
st = SegTree(n+1);
st.build(dp_prev);
vector<int> stk, left(n+1);
for (int i = k; i <= n; i++) dp_cur[i] = INF;
for (int i = k; i <= n; i++) {
int L = i;
while (!stk.empty() && a[stk.back()] <= a[i]) {
int t = stk.back(); stk.pop_back();
int lt = left[t];
st.range_add(lt-1, t-1, -a[t]);
L = lt;
}
stk.push_back(i);
left[i] = L;
st.range_add(L-1, i-1, a[i]);
dp_cur[i] = st.range_min(k-1, i-1);
}
dp_prev.swap(dp_cur);
}
cout << dp_prev[n] << "\n";
return 0;
}
