#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
// Segment tree supporting range-add and range-min queries
struct SegTree {
int n;
vector<ll> st, lazy;
SegTree(int _n) : n(_n), st(4 * n, INF), lazy(4 * n, 0) {}
void apply(int p, int l, int r, ll v) {
st[p] += v;
lazy[p] += v;
}
void push(int p, int l, int r) {
if (lazy[p] != 0) {
int m = (l + r) >> 1;
apply(p << 1, l, m, lazy[p]);
apply(p << 1 | 1, m + 1, r, lazy[p]);
lazy[p] = 0;
}
}
void pull(int p) {
st[p] = min(st[p << 1], st[p << 1 | 1]);
}
void build(int p, int l, int r, const vector<ll>& base) {
if (l == r) {
st[p] = base[l];
return;
}
int m = (l + r) >> 1;
build(p << 1, l, m, base);
build(p << 1 | 1, m + 1, r, base);
pull(p);
}
void range_add(int p, int l, int r, int i, int j, ll v) {
if (i > r || j < l) return;
if (i <= l && r <= j) {
apply(p, l, r, v);
return;
}
push(p, l, r);
int m = (l + r) >> 1;
range_add(p << 1, l, m, i, j, v);
range_add(p << 1 | 1, m + 1, r, i, j, v);
pull(p);
}
ll range_min(int p, int l, int r, int i, int j) {
if (i > r || j < l) return INF;
if (i <= l && r <= j) return st[p];
push(p, l, r);
int m = (l + r) >> 1;
return min(
range_min(p << 1, l, m, i, j),
range_min(p << 1 | 1, m + 1, r, i, j)
);
}
};
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];
// dp_prev[j]: best cost for up to j with prev segments
vector<ll> dp_prev(n + 1, INF), dp_cur(n + 1, INF);
dp_prev[0] = 0;
// Base case k=1: prefix max
for (int i = 1; i <= n; i++) {
dp_prev[i] = max(dp_prev[i - 1], a[i]);
}
for (int k = 2; k <= K; k++) {
// Build segment tree on dp_prev
SegTree st(n + 1);
st.build(1, 0, n, dp_prev);
vector<int> stk, left(n + 1);
stk.reserve(n);
fill(dp_cur.begin(), dp_cur.end(), INF);
for (int i = 1; i <= n; i++) {
int L = i;
// Pop smaller or equal elements, update range
while (!stk.empty() && a[stk.back()] <= a[i]) {
int t = stk.back(); stk.pop_back();
int lt = left[t];
st.range_add(1, 0, n, lt - 1, t - 1, a[i] - a[t]);
L = lt;
}
stk.push_back(i);
left[i] = L;
// Query best dp for pos i with k segments
dp_cur[i] = st.range_min(1, 0, n, 0, i - 1);
}
dp_prev.swap(dp_cur);
}
cout << dp_prev[n] << '\n';
return 0;
}
