#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a) (int)a.size()
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector <int> a(n + 1), dp(n + 1);
F(i, 1, n) cin >> a[i], dp[i] = max(dp[i - 1], a[i]);
F(_k, 2, k) {
vector <int> tdp(n + 1, 2e9);
stack <array <int, 2>> s;
F(i, _k, n) {
int min_f = dp[i - 1];
while(N(s) && a[s.top()[0]] <= a[i]) {
min_f = min(min_f, s.top()[1]);
s.pop();
}
tdp[i] = min_f + a[i];
if(N(s)) tdp[i] = min(tdp[i], tdp[s.top()[0]]);
s.push({i, min_f});
}
swap(tdp, dp);
}
cout << dp[n];
return 0;
}
