// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node{
ll s, e, m, val, lz;
node *l, *r;
node (int _s, int _e) {
s = _s, e = _e, m = (s + e) >> 1;
if (s != e) {
l = new node(s, m);
r = new node(m + 1, e);
}
val = lz = 0;
}
void prop(){
if (lz) {
val += lz;
if (s != e) l->lz += lz, r->lz += lz;
lz = 0;
}
}
void upd(int a, int b, ll c){
if (a == s && b == e) lz += c;
else {
if (b <= m) l->upd(a, b, c);
else if (a > m) r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m + 1, b, c);
l->prop(), r->prop();
val = min(l->val, r->val);
}
}
ll qry(int a, int b){
prop();
if (a == s && b == e) return val;
else if (b <= m) return l->qry(a, b);
else if (a > m) return r->qry(a, b);
else return min(l->qry(a, m), r->qry(m + 1, b));
}
}*root;
ll a[100005], dp[105][100005];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
dp[0][0] = 0;
root = new node(1, n);
for (int i = 1; i <= n; i++) dp[0][i] = 1e14;
for (int i = 1; i <= k; i++) dp[i][0] = 1e14;
for (int i = 1; i <= k; i++) {
stack <int> s;
s.push(0);
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j - 1] + a[j];
while (s.size() > 1) {
int x = s.top();
if (a[x] < a[j]) {
s.pop();
//root->upd(s.top() + 1, x, a[j] - a[x]);
dp[i][j] = min(dp[i][j], dp[i][x] + a[j] - a[x]);
}
else {
dp[i][j] = min(dp[i][j], dp[i][s.top()]);
break;
}
}
s.push(j);
//root->upd(j, j, dp[i - 1][j - 1] + a[j] - root->qry(j, j));
//dp[i][j] = root->qry(1, j);
}
}
cout << dp[k][n];
}
