#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll INF = (1LL<<60);
static const int MAXN = 100000;
// --- segment tree range-add + global-min ---
struct Seg {
struct Node { ll mn, lz; } st[4*MAXN];
// build không cần, vì ta khởi lại bằng memset
inline void apply(int p, ll v) {
st[p].mn += v;
st[p].lz += v;
}
inline void push(int p) {
if (st[p].lz) {
apply(p<<1, st[p].lz);
apply(p<<1|1, st[p].lz);
st[p].lz = 0;
}
}
inline void pull(int p) {
st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
}
// update range [i..j] += v
void updR(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;
if (i <= m) updR(p<<1, l, m, i, j, v);
if (j > m) updR(p<<1|1, m+1, r, i, j, v);
pull(p);
}
// point set pos=idx to value (overwrite)
void updP(int p, int l, int r, int idx, ll val) {
if (l==r) {
st[p].mn = val;
st[p].lz = 0;
return;
}
push(p);
int m = (l+r)>>1;
if (idx <= m) updP(p<<1, l, m, idx, val);
else updP(p<<1|1, m+1, r, idx, val);
pull(p);
}
inline ll query() const {
return st[1].mn;
}
} seg;
// --- globals ---
int N, K;
int A[MAXN+1];
ll dp_prev[MAXN+1], dp_cur[MAXN+1];
// stack: values và left‑indices
int stk_val[MAXN+1], stk_lft[MAXN+1], stk_sz;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for(int i = 1; i <= N; ++i)
cin >> A[i];
// init dp_prev
for(int i = 0; i <= N; ++i)
dp_prev[i] = (i==0 ? 0 : INF);
while(K--){
// reset segtree nodes [1..4N]
memset(seg.st, 0x7f, sizeof seg.st);
// xây lại mn = INF, lz = 0
for(int p = 1; p < 4*(N+1); ++p){
seg.st[p].mn = INF;
seg.st[p].lz = 0;
}
stk_sz = 0;
// i = 1 khởi tạo
seg.updP(1, 0, N-1, 0, dp_prev[0]);
stk_val[0] = A[1];
stk_lft[0] = 0;
stk_sz = 1;
seg.updR(1, 0, N-1, 0, 0, A[1]);
for(int i = 1; i <= N; ++i){
if (i > 1){
// 1) set dp_prev[i-1]
seg.updP(1, 0, N-1, i-1, dp_prev[i-1]);
// 2) xử lý A[i] với monotonic stack
int L = i - 1;
while(stk_sz > 0 && stk_val[stk_sz-1] <= A[i]){
int v = stk_val[stk_sz-1];
int lf = stk_lft[stk_sz-1];
--stk_sz;
seg.updR(1, 0, N-1, lf, L-1, -v);
L = lf;
}
// push segment mới
stk_val[stk_sz] = A[i];
stk_lft[stk_sz] = L;
++stk_sz;
seg.updR(1, 0, N-1, L, i-1, A[i]);
}
dp_cur[i] = seg.query();
}
// swap dp_prev / dp_cur
memcpy(dp_prev, dp_cur, (N+1)*sizeof ll);
}
cout << dp_prev[N];
return 0;
}
