#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
ll mod = 1e9 + 7;
ll gcd(ll a, ll b) {
if (b == 0)return a;
else return gcd(b, a % b);
}
void solve() {
ll n, k; cin >> n >> k;
vector<ll>v(n + 1);
for (ll i = 1; i <= n; i++) {
cin >> v[i];
}
stack<pair<ll, ll>>st;
vector<ll>mec(n + 1, 0);
for (ll i = 1; i <= n; i++) {
while (st.size() && st.top().first <= v[i]) {
st.pop();
}
if (st.size()) {
mec[i] = st.top().second;
}
st.push({ v[i],i });
}
//for (ll i = 1; i <= n; i++)cout << mec[i] << " ";
//cout << endl;
vector<vector<vector<ll>>>dp(n + 1, vector<vector<ll>>(k + 1, vector<ll>(2, 1e18)));
dp[0][0][0] = 0;
dp[0][0][1] = 0;
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= k; j++) {
ll urde = mec[i];
dp[i][j][1] = min(dp[i][j][1], dp[max(j - 1, urde)][j - 1][1] + v[i]);
dp[i][j][1] = min(dp[i][j][1], dp[max(j - 1, urde)][j - 1][0] + v[i]);
dp[i][j][0] = min(dp[i][j][0], dp[urde][j][1]);
dp[i][j][0] = min(dp[i][j][0], dp[urde][j][0]);
}
}
cout << min(dp[n][k][0], dp[n][k][1]) << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
ll t = 1;
//cin >> t;
while (t--) {
solve();
}
}
