#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
struct SegTree {
int n;
vector<ll> st, lz;
SegTree(int _n): n(_n), st(4*n, INF), lz(4*n, 0) {}
void apply(int p, ll v) {
st[p] += v;
lz[p] += v;
}
void push(int p) {
if (lz[p]) {
apply(p<<1, lz[p]);
apply(p<<1|1, lz[p]);
lz[p] = 0;
}
}
void pull(int p) {
st[p] = min(st[p<<1], st[p<<1|1]);
}
void update_range(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, v);
return;
}
push(p);
int m=(l+r)>>1;
update_range(p<<1, l, m, i, j, v);
update_range(p<<1|1, m+1, r, i, j, v);
pull(p);
}
void update_point(int p, int l, int r, int idx, ll value) {
if (l==r) {
st[p] = value;
lz[p] = 0;
return;
}
push(p);
int m=(l+r)>>1;
if (idx<=m) update_point(p<<1, l, m, idx, value);
else update_point(p<<1|1, m+1, r, idx, value);
pull(p);
}
ll query_min() {
return st[1];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
vector<int> A(N+1);
for(int i=1;i<=N;i++) cin >> A[i];
vector<ll> dp_prev(N+1, INF), dp_cur(N+1, INF);
dp_prev[0] = 0;
for(int k=1;k<=K;k++){
SegTree st(N);
vector<pair<int,int>> stk;
stk.reserve(N);
st.update_point(1, 0, N-1, 0, dp_prev[0]);
stk.emplace_back(A[1], 0);
st.update_range(1, 0, N-1, 0, 0, A[1]);
for(int i=1;i<=N;i++){
if (i>1) {
st.update_point(1, 0, N-1, i-1, dp_prev[i-1]);
int L = i-1;
while(!stk.empty() && stk.back().first <= A[i]){
auto [v, lft] = stk.back();
stk.pop_back();
st.update_range(1, 0, N-1, lft, L-1, -v);
L = lft;
}
stk.emplace_back(A[i], L);
st.update_range(1, 0, N-1, L, i-1, A[i]);
}
dp_cur[i] = st.query_min();
}
dp_prev = dp_cur;
fill(dp_cur.begin(), dp_cur.end(), INF);
}
cout << dp_prev[N] << "\n";
return 0;
}
