#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5, K = 101;
int n, k;
int a[N];
long long dp[N][K], f[N][K];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
memset(f, 0x3f, sizeof(f));
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
vector<int> st;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
f[i][j] = dp[i - 1][j];
}
while (st.size() && a[st.back()] <= a[i]) {
for (int j = 0; j <= k; ++j) {
f[i][j] = min(f[i][j], f[st.back()][j]);
}
st.pop_back();
}
for (int j = 1; j <= k; ++j) {
dp[i][j] = min(dp[i][j], f[i][j - 1] + a[i]);
}
if (st.size()) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = min(dp[i][j], dp[st.back()][j]);
}
}
st.push_back(i);
}
cout << dp[n][k];
return 0;
}
