#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define uni(a) sort(all(a)), a.resize(unique(all(a)) - a.begin())
typedef pair <int, int> ii;
const int N = 1e5 + 5;
int n, k, a[N], ans, l[N], r[N];
stack <int> st;
struct segtree {
int seg[N << 2], lazy[N << 2];
void reset() {
for (int i = 1; i <= (n << 2); i++) {
lazy[i] = seg[i] = 1e9;
}
}
void apply(int id, int val) {
seg[id] = min(seg[id], val);
lazy[id] = min(lazy[id], val);
}
void push(int id) {
if (lazy[id] == 1e9) return;
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 1e9;
}
void up(int l, int r, int id, int u, int v, int val) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
apply(id, val);
return;
}
push(id);
int mid = (l + r) >> 1;
up(l, mid, id << 1, u, v, val);
up(mid + 1, r, id << 1 | 1, u, v, val);
seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}
void up(int l, int r, int val) {
up(0, n, 1, l, r, val);
}
int get(int l, int r, int id, int u, int v) {
if (l > v || r < u) return 1e9;
if (l >= u && r <= v) return seg[id];
push(id);
int mid = (l + r) >> 1;
return min(get(l, mid, id << 1, u, v), get(mid + 1, r, id << 1 | 1, u, v));
}
int get(int l, int r) {
return get(0, n, 1, l, r);
}
} seg[2];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("a.inp", "r", stdin);
//freopen("a.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[0] = a[n + 1] = 1e9;
st.push(0);
for (int i = 1; i <= n; i++) {
while (a[st.top()] <= a[i]) st.pop();
l[i] = st.top();
st.push(i);
}
while (sz(st)) st.pop();
st.push(n + 1);
for (int i = n; i >= 1; i--) {
while (a[st.top()] <= a[i]) st.pop();
r[i] = st.top();
st.push(i);
}
seg[0].reset(); seg[0].up(0, 0, 0);
for (int j = 1; j <= k; j++) {
seg[j & 1].reset();
for (int i = 1; i <= n; i++) {
seg[j & 1].up(i, r[i] - 1, seg[(j - 1) & 1].get(l[i], i - 1) + a[i]);
}
}
cout << seg[k & 1].get(n, n) << '\n';
return 0;
}
