#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x) (x).begin(), (x).end()
#define inf 1e18
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector <ll> v(n);
for (auto &i : v) cin >> i;
vector < vector <ll> > dp(n + 1, vector <ll> (k + 1));
for (int i = 1; i <= n; ++i) dp[i][0] = inf;
stack < pair <ll, ll> > st;
for (int i = 1; i <= k; ++i) {
while (!st.empty()) st.pop();
dp[i][i] = dp[i - 1][i - 1] + v[i - 1]; st.push({v[i - 1], dp[i - 1][i - 1]});
for (int j = i + 1; j <= n; ++j) {
ll c = dp[j - 1][i - 1];
while (!st.empty() && st.top().fi <= v[j - 1]) {
c = min(c, st.top().se);
st.pop();
}
if (st.empty() || st.top().fi + st.top().se > v[j - 1] + c) st.push({v[j - 1], c});
dp[j][i] = st.top().fi + st.top().se;
}
}
cout << dp[n][k];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// ifstream cin("input.txt");
// ofstream cout("output.txt");
int q = 1; // cin >> q;
while (q--) solve();
}
