#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
using ll = long long;
const int mod = 1e9+7;
void solve(int tc) {
int n, k;
cin >> n >> k;
vector<int> v(n+1), prev(n+1);
for (int i = 1; i <= n; ++i) {
cin >> v[i];
int p = i-1;
while (p and v[p] < v[i]) p = prev[p];
prev[i] = p;
}
vector<vector<int>> dp(n+1, vector<int>(k+1, (1<<30)));
dp[0][0] = 0;
vector<int> s(n+1);
for (int j = 1; j <= k; ++j) {
int l = 0;
for (int i = 0; i < j; ++i) {
while (l and dp[s[l-1]][j-1] >= dp[i][j-1]) --l;
s[l++] = i;
}
for (int i = j; i <= n; ++i) {
int p = lower_bound(s.begin(), s.begin() + l, prev[i]) - s.begin();
dp[i][j] = min(v[i] + dp[s[p]][j-1], dp[prev[i]][j]);
while (l and dp[s[l-1]][j-1] >= dp[i][j-1]) --l;
s[l++] = i;
}
}
cout << dp[n][k] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int tc = 1;
//cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
