#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 100100;
const int K = 110;
const int PW = 20;
stack<pi3> st;
int f[N][K], a[N], n, k;
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = oo;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
f[i][j] = oo;
f[0][0] = 0;
for (int j = 1; j <= k; j++) {
while (sz(st)) st.pop();
st.push(MP3(0, oo, oo));
for (int i = 1; i <= n; i++){
pi3 nw = MP3(i, f[i - 1][j - 1], 0);
while (a[st.top().ft.ft] <= a[i]) {
nw.ft.sd = min(nw.ft.sd, st.top().ft.sd);
st.pop();
}
nw.sd = min(st.top().sd, nw.ft.sd + a[i]);
st.push(nw);
f[i][j] = nw.sd;
}
}
cout << f[n][k];
return 0;
}
