#include <bits/stdc++.h>
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e5+3;
int n, k, a[N];
int dp[N], dp2[N];
struct Lazy{
//todo: write apply function, clear lazy function
vector<int> tree, lazy;
void resize(int n){
tree.assign(n<<2+3, 0);
lazy.assign(n<<2+3, 0);
}
void apply(int id, int len, int add){
//do something (both tree and lazy)
tree[id] += add; lazy[id] += add;
}
void push(int id, int l, int r){
int mid = (l+r)/2;
apply(id << 1, mid - l + 1, lazy[id]);
apply(id << 1 | 1, r - mid, lazy[id]);
//clear lazy
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int tmp){
if(v < l || r < u) return ;
if(u <= l && r <= v){
apply(id, r-l+1, tmp);
return ;
}
push(id, l, r);
int mid = (l+r)/2;
update(id<<1, l, mid, u, v, tmp);
update(id<<1|1, mid+1, r, u, v, tmp);
tree[id] = min(tree[id<<1], tree[id<<1|1]);
}
int get(int id, int l, int r, int u, int v){
if(v < l || r < u) return 1e9;
if(u <= l && r <= v) return tree[id];
push(id, l, r);
int mid = (l+r)/2;
int lf = get(id<<1, l, mid, u, v);
int rg = get(id<<1|1, mid+1, r, u, v);
return min(lf, rg);
}
} t;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
memset(dp2, 0x3f, sizeof(dp2));
dp2[0] = 0;
for(int j = 1; j <= k; j++){
t.resize(n);
for(int i = 1; i <= n; i++) t.update(1, 1, n, i, i, dp2[i-1]);
stack<pair<int, int>> st;
for(int i = 0; i <= n; i++) dp[i] = 1e9;
for(int i = 1; i <= n; i++){
int pos = i;
while(!st.empty() && st.top().first <= a[i]){
int val = st.top().first;
int l = st.top().second;
st.pop();
if(l < pos){
t.update(1, 1, n, l, pos-1, a[i]-val);
}
pos = l;
}
st.push(make_pair(a[i], pos));
t.update(1, 1, n, i, i, a[i]);
dp[i] = t.get(1, 1, n, 1, i);
}
// for(int i = 0; i <= n; i++) cout << (dp[i]>=1e9?-1:dp[i]) << " ";
// cout << "\n";
for(int i = 0; i <= n; i++) dp2[i] = dp[i];
}
cout << dp[n];
return 0;
}
