#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int INF = 1e9;
const int MAXN = 100005;
int n, k;
int a[MAXN];
int dp[MAXN], next_dp[MAXN];
// Segment Tree strukturasi minimal qiymatlarni saqlash uchun
int tree[4 * MAXN], lazy[4 * MAXN];
void push(int v) {
if (lazy[v] != 0) {
tree[2 * v] += lazy[v];
lazy[2 * v] += lazy[v];
tree[2 * v + 1] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
}
void update(int v, int tl, int tr, int l, int r, int add) {
if (l > r) return;
if (l == tl && r == tr) {
tree[v] += add;
lazy[v] += add;
} else {
push(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, min(r, tm), add);
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
}
void build(int v, int tl, int tr, int* source_dp) {
lazy[v] = 0;
if (tl == tr) {
tree[v] = source_dp[tl];
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm, source_dp);
build(2 * v + 1, tm + 1, tr, source_dp);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> k)) return 0;
for (int i = 1; i <= n; i++) cin >> a[i];
// Dastlabki holat: 1 ta blokka bo'lish (k=1)
int current_max = 0;
for (int i = 1; i <= n; i++) {
current_max = max(current_max, a[i]);
dp[i] = current_max;
}
// Har bir keyingi blok uchun DP qatlamini yangilaymiz
for (int j = 2; j <= k; j++) {
build(1, 0, n - 1, dp);
stack<int> s;
for (int i = 1; i <= n; i++) {
// Monoton stack yordamida maksimal element diapazonini aniqlaymiz
while (!s.empty() && a[s.top()] <= a[i]) {
int last = s.top();
s.pop();
int prev = s.empty() ? 0 : s.top();
update(1, 0, n - 1, prev, last - 1, a[i] - a[last]);
}
s.push(i);
// Segment treedan minimal dp[j-1][p] + max(p+1...i) qiymatni olamiz
update(1, 0, n - 1, i - 1, i - 1, a[i]);
next_dp[i] = tree[1];
}
for (int i = 1; i <= n; i++) dp[i] = next_dp[i];
}
cout << dp[n] << endl;
return 0;
}
