#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
vector<vector<long long>> dp(k, vector<long long> (n));
for (int i = 0; i < n; ++i) {
cin >> a[i];
dp[0][i] = a[i];
if (i) {
dp[0][i] = max(dp[0][i], dp[0][i - 1]);
}
}
for (int j = 1; j < k; ++j) {
stack<pair<int, long long>> stk;
for (int i = j; i < n; ++i) {
long long x = dp[j - 1][i - 1];
while (!stk.empty() && stk.top().second <= a[i]) {
x = min(x, stk.top().second);
stk.pop();
}
if (stk.empty() || (stk.top().first + stk.top().second > a[i] + x)) {
stk.push({a[i], x});
}
dp[j][i] = stk.top().first + stk.top().second;
//deb(stk.top());deb(dp[j][i]); cout << '\n';
}
}
cout << dp[k - 1][n - 1] << '\n';
return 0;
}
