#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 200;
const int INF = 1e9+1e2;
void fin() {
#ifdef AM
freopen(".in", "r", stdin);
#endif
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr), fin();
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) {
cin >> x;
}
vector<int> dp(n), dp_new(n);
for (int i = 0; i < n; ++i) {
dp[i] = max((i ? dp[i-1] : 0), a[i]);
}
for (int j = 2; j <= k; ++j) {
stack<pii> s;
for (int i = 0; i < n; ++i) {
dp_new[i] = INF;
}
for (int i = j-1; i < n; ++i) {
int mn = dp[i-1];
while (!s.empty() && s.top().x <= a[i]) {
mn = min(mn, s.top().y);
s.pop();
}
if (s.empty() || s.top().x + s.top().y > mn + a[i]) {
s.push({a[i], mn});
}
dp_new[i] = s.top().x + s.top().y;
}
swap(dp, dp_new);
}
cout << dp[n-1];
return 0;
}
