#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
using namespace std;
void read(int &n) {
n = 0;
char c = getchar();
while(isdigit(c)) {
(n *= 10) += c - '0';
c = getchar();
}
}
const int maxn = 2e5 + 1;
int n, k, cnt, min_f, a[maxn], s[maxn][2], dp[maxn], tdp[maxn];
int main() {
read(n), read(k);
F(i, 1, n) read(a[i]), dp[i] = max(dp[i - 1], a[i]);
F(_k, 2, k) {
cnt = 0;
memset(tdp, 63, sizeof tdp);
F(i, _k, n) {
min_f = dp[i - 1];
while(cnt && a[s[cnt][0]] <= a[i]) {
min_f = min(min_f, s[cnt][1]);
--cnt;
}
tdp[i] = min_f + a[i];
if(cnt) tdp[i] = min(tdp[i], tdp[s[cnt][0]]);
s[++cnt][0] = i, s[cnt][1] = min_f;
}
swap(tdp, dp);
}
cout << dp[n];
return 0;
}
