#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int a[N];
struct T {
ll v;
ll v2;
int l;
bool kt;
} st[4*N];
int L[N];
int n, k;
ll dp[105][N];
int lg[N];
inline void down(int id) {
if (st[id].kt) {
int& t = st[id].l;
st[2*id].kt = 1;
st[2*id].v = st[2*id].v2 + t;
st[2*id].l = t;
st[2*id+1].kt = 1;
st[2*id+1].v = st[2*id+1].v2 + t;
st[2*id+1].l = t;
st[id].kt = 0;
}
}
void upd1(int id, int l, int r, int u, int v, int k) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id].kt = 1;
st[id].v = st[id].v2 + k;
st[id].l = k;
return;
}
int mid = (l+r)/2;
down(id);
upd1(2*id, l, mid, u, v, k);
upd1(2*id+1, mid+1, r, u, v, k);
st[id].v2 = min(st[2*id].v2, st[2*id+1].v2);
st[id].v = min(st[2*id].v, st[2*id+1].v);
}
void upd2(int id, int l, int r, int i, ll v) {
if (l > i || r < i) return;
if (l == r) {
st[id].v2 = v;
st[id].v = v;
return;
}
int mid = (l+r)/2;
down(id);
upd2(2*id, l, mid, i, v);
upd2(2*id+1, mid+1, r, i, v);
st[id].v2 = min(st[2*id].v2, st[2*id+1].v2);
st[id].v = min(st[2*id].v, st[2*id+1].v);
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 1e18;
if (l >= u && r <= v) return st[id].v;
int mid = (l+r)/2;
down(id);
int x = get(2*id, l, mid, u, v);
int y = get(2*id+1, mid+1, r, u, v);
return min(x, y);
}
void prep() {
stack<int> st;
for (int i = 1; i <= n; i++) {
while (st.size() && a[st.top()] <= a[i]) st.pop();
if (st.size()) L[i] = st.top();
st.push(i);
}
}
signed main() {
if (fopen("I.inp", "r")) {
freopen("I.inp", "r", stdin);
freopen("I.out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
prep();
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 1e18;
}
}
dp[0][0] = 0;
for (int i = 1; i <= k; i++) {
fill(st, st+4*N, T{0, 0, 0, 0});
for (int j = 1; j <= n; j++) {
upd1(1, 0, n, L[j], j-1, a[j]);
if (j >= i) {
dp[i][j] = get(1, 0, n, i-1, j-1);
}
upd2(1, 0, n, j, dp[i-1][j]);
}
}
cout << dp[k][n];
return 0;
}
