#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000;
int n, k;
int a[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<vector<long long>> f(k + 10, vector<long long>(n + 10, MAX));
f[0][0] = 0;
for (int i = 1; i <= k; ++i) {
vector<long long> g(n + 10, MAX);
stack<int> st;
for (int j = 1; j <= n; ++j) {
auto& ret = f[i][j];
g[j] = f[i - 1][j - 1];
while (st.size() && a[st.top()] <= a[j]) {
g[j] = min(g[j], g[st.top()]);
st.pop();
}
ret = g[j] + a[j];
if (st.size()) ret = min(ret, f[i][st.top()]);
st.push(j);
}
}
cout << f[k][n] << "\n";
}
