#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define int ll
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
#define en "\n"
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<pii>;
vvi dp; //prawdziwe dp
vvi p; //pomocnicze tu suf
void solve() {
int n, k;
cin >> n >> k;
vi a(n + 1);
f(i, 1, n+1)cin >>a[i];
a[0] = DUZO;
dp.resize(n + 1, vi(k + 1, DUZO));
p.resize(n + 1, vi(k + 1, DUZO));
dp[0][0] = 0;
p[0][0] = 0;
stack<int> stos;
stos.push(0);
f(i, 1, n + 1) {
while (a[stos.top()] < a[i]) {
int ind = stos.top();
stos.pop();
int nw = stos.top();
f(j, 0, k + 1) {
p[nw][j] = min(p[nw][j], p[ind][j]);
}
}
int ind = stos.top();
stos.push(i);
dp[i][0] = DUZO;
f(j, 1, k + 1) {
dp[i][j] = min(dp[ind][j], a[i] + p[ind][j - 1]);
p[i][j] = dp[i][j];
}
}
cout<<dp.back().back()<<en;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int q = 1;
//cin >> q;
while (q--) {
solve();
}
return 0;
}
