#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
template<class T>
int chmax(T &x, T y) {
if (x < y) {
x = y;
return 1;
}
return 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
vector<ll> a(n);
for (ll &x : a) cin >> x;
auto check = [&] (ll x) {
vector<array<pair<ll, int>, 2>> dp(n + 1, {{{-INF, 0}, {-INF, 0}}});
dp[0][0] = {0, 0};
for (int i = 0; i < n; i++) {
chmax(dp[i][0], dp[i][1]);
if (chmax(dp[i][1].first, dp[i][0].first - x)) dp[i][1].second = dp[i][0].second + 1;
chmax(dp[i + 1][0], dp[i][0]);
if (chmax(dp[i + 1][1].first, dp[i][1].first + a[i])) dp[i + 1][1].second = dp[i][1].second;
}
return max(dp[n][0], dp[n][1]);
};
ll lo = 0, hi = 1e12 + 5;
while (hi - lo > 1) {
ll m = (lo + hi) / 2;
if (check(m).second >= k + 1) lo = m;
else hi = m;
}
auto [cost, taken] = check(lo);
cout << (cost + k * lo) << '\n';
}
