#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MXN = 1e5+5;
int n, k, a[MXN], L[MXN], R[MXN], lc[MXN], rc[MXN], dp[2][MXN];
inline pii gp(int i) { return pii(a[i], i); }
int calc(int i, int val) {
if(lc[i]) {
int mnl = calc(lc[i], val);
dp[1][i] = min(val, mnl+a[i]);
if(rc[i])
return min({mnl, dp[0][i], calc(rc[i], min(dp[1][i], dp[0][L[i]]+a[i]))});
return min(mnl, dp[0][i]);
}
dp[1][i] = min(val, dp[0][i-1]+a[i]);
if(rc[i])
return min(dp[0][i], calc(rc[i], dp[1][i]));
return dp[0][i];
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> k;
for(int i=1; i<=n; i++) {
cin >> a[i];
dp[1][i] = max(dp[1][i-1], a[i]);
for(L[i]=i-1; L[i]>=1 && gp(L[i])<gp(i); L[i]=L[L[i]]);
}
for(int i=n; i>=1; i--)
for(R[i]=i+1; R[i]<=n && gp(R[i])<gp(i); R[i]=R[R[i]]);
int root = 0;
for(int i=1; i<=n; i++)
if(L[i]==0) {
if(R[i]==n+1) root=i;
else lc[R[i]] = i;
}
else if(R[i]==n+1 || gp(L[i])<gp(R[i])) rc[L[i]] = i;
else lc[R[i]] = i;
dp[0][0] = dp[1][0] = 1e9;
for(int i=2; i<=k; i++) {
for(int j=1; j<=n; j++)
dp[0][j] = dp[1][j],
dp[1][j] = 1e9;
calc(root, 1e9);
}
cout << dp[1][n] << '\n';
}
