#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int &i : a) cin >> i;
auto dp = a;
for (int i = 1; i < n; i++) dp[i] = max(dp[i - 1], dp[i]);
const int inf = 1e9;
auto new_dp = dp;
for (int _ = 1; _ < k; _++) {
for (int i = 0; i < n; i++) new_dp[i] = inf;
stack<int> s, t;
for (int i = 0; i < n; i++) {
int mx = inf;
while (!s.empty() && a[s.top()] <= a[i]) {
mx = min(mx, t.top());
t.pop();
s.pop();
}
new_dp[i] = min(new_dp[i], mx + a[i]);
if (!s.empty()) {
new_dp[i] = min(new_dp[i], dp[s.top()] + a[i]);
new_dp[i] = min(new_dp[i], new_dp[s.top()]);
}
mx = min(mx, dp[i]);
s.push(i);
t.push(mx);
}
swap(dp, new_dp);
}
cout << dp[n - 1];
return 0;
}
