#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<long long, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))
#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';
const int MAXN = 1e5 + 5;
const int MAXK = 500 + 5;
const long long INF = 1e15 + 5;
int n, k, a[MAXN];
long long dp[MAXN][MAXK];
void solve() {
for (int i = 0; i < MAXN; ++i)
for (int j = 0; j < MAXK; ++j)
dp[i][j] = INF;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
dp[0][0] = 0;
// Get min at dp[j - 1][j - 1];
int cur = 0;
for (int i = 1; i <= n; ++i) {
cur = max(cur, a[i]);
dp[i][1] = cur;
}
vector<pii> st;
for (int j = 2; j <= k; ++j) {
for (int i = j; i <= n; ++i) {
// int mx = 0;
// for (int t = j; t <= i; ++t) mx = max(mx, a[t]);
// dp[i][j] = dp[j - 1][j - 1] + mx;
long long cand = dp[i - 1][j - 1];
while (!st.empty() && a[st.back().se] <= a[i]) {
cand = min(cand, st.back().fi);
st.pop_back();
}
dp[i][j] = min(dp[st.empty() ? 0 : st.back().se][j], cand + a[i]);
st.push_back({cand, i});
// int mx = a[i];
// // cout << "State " << i << ' ' << j << ": \n";
// int mii = 0, mij = 0;
// for (int pre = i - 1; pre >= 0; --pre) {
// if (dp[pre][j - 1] + mx < dp[i][j]) {
// mii = pre; mij = j - 1;
// }
// dp[i][j] = min(dp[i][j], dp[pre][j - 1] + mx);
// // cout << "pre = " << pre << ": " << dp[pre][j - 1] + mx << '\n';
// mx = max(mx, a[pre]);
// }
// // cout << "Minimum at " << mii << ' ' << mij << '\n';
}
st.clear();
}
cout << dp[n][k];
}
signed main() {
#ifdef NCTHANH
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
