#include <bits/stdc++.h>
#define int long long
#define fr first
#define sc second
using namespace std;
const int mx = 1e5 + 5;
int n, k;
int a[mx];
vector <int> dp, tp;
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
tp = vector<int>(n + 1, 2000000);
tp[0] = 0;
for (int j = 1; j <= k; j++) {
dp = vector<int>(n + 1);
vector <tuple <int, int, int>> stk;
vector <pair <int, int>> dtk;
for (int i = j-1; i >= 1; i--) {
tp[i-1] = min(tp[i-1], tp[j]);
}
for (int i = j; i <= n; i++) {
int tpm = tp[i-1];
while (stk.size() && get<0>(stk.back()) <= a[i]) {
tpm = min(tpm, get<1>(stk.back()));
stk.pop_back();
}
while (dtk.size() && a[dtk.back().sc] < a[i]) {
dtk.pop_back();
}
if (dtk.empty() || tpm + a[i] < dtk.back().fr + a[dtk.back().sc]) {
dtk.emplace_back(tpm, i);
}
dp[i] = dtk.back().fr + a[dtk.back().sc];
stk.emplace_back(a[i], tpm, i);
}
tp = dp;
}
cout << dp[n] << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
