#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int read_int(){
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
return result;
}
typedef long long int64;
const int64 INF = 1e16 + 3;
struct SegmentTree {
vector<int64> tree, lazy;
SegmentTree (int n) : tree(n << 2 | 3, INF), lazy(n << 2 | 3, 0) {}
void reload() {
fill(tree.begin(), tree.end(), INF);
fill(lazy.begin(), lazy.end(), 0);
}
void apply(int id, int64 x) {
tree[id] += x;
lazy[id] += x;
}
void push(int id) {
if(lazy[id]) {
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
}
void update(int id, int l, int r, int p, int64 x) {
if(l == r) return tree[id] = x, void();
int mid = (l + r) >> 1;
push(id);
if(p <= mid) update(id << 1, l, mid, p, x);
else update(id << 1 | 1, mid + 1, r, p, x);
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
void update(int id, int l, int r, int u, int v, int64 x) {
if(r < u || v < l) return void();
if(u <= l && r <= v) return apply(id, x), void();
int mid = (l + r) >> 1;
push(id);
update(id << 1, l, mid, u, v, x);
update(id << 1 | 1, mid + 1, r, u, v, x);
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
int64 get(int id, int l, int r, int u, int v) {
if(r < u || v < l) return INF;
if(u <= l && r <= v) return tree[id];
int mid = (l + r) >> 1;
push(id);
return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n = read_int();
int k = read_int();
vector<int> nums(n + 1);
for(int i = 1; i <= n; i++) {
nums[i] = read_int();
}
SegmentTree seg(n);
vector<vector<int64>> dp(n + 1, vector<int64>(k + 1, INF));
dp[0][0] = 0;
for(int t = 1; t <= k; t++) {
stack<int> mono;
seg.reload();
for(int i = t; i <= n; i++) {
seg.update(1, 1, n, i, dp[i - 1][t - 1]);
while(!mono.empty() && nums[i] > nums[mono.top()]) {
int p = mono.top(); mono.pop();
seg.update(1, 1, n, (mono.empty() ? 0 : mono.top()) + 1, p, -nums[p]);
}
seg.update(1, 1, n, (mono.empty() ? 0 : mono.top()) + 1, i, nums[i]);
mono.push(i);
dp[i][t] = seg.get(1, 1, n, 1, i);
}
}
cout << dp[n][k] << "\n";
return 0;
}
