#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct State {
int64_t score;
int segs;
bool operator<(const State &o) const {
if (score != o.score) return score < o.score;
return segs > o.segs;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<int64_t> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
auto solve = [&](int64_t C) -> State {
State dp0 = {0, 0};
State dp1 = {(int64_t) -1e16, 0};
for (int i = 1; i <= n; i++) {
State next_dp0 = max(dp0, dp1);
State start_new = {dp0.score + a[i] - C, dp0.segs + 1};
State cont_curr = {dp1.score + a[i], dp1.segs};
State next_dp1 = max(start_new, cont_curr);
dp0 = next_dp0;
dp1 = next_dp1;
}
return max(dp0, dp1);
};
State unconstrained = solve(0);
if (unconstrained.segs <= k) {
cout << unconstrained.score << "\n";
return 0;
}
int64_t l = 1, r = 3e14, ans = 0;
while (l <= r) {
int64_t mid = l + (r - l) / 2;
State res = solve(mid);
if (res.segs > k) {
l = mid + 1;
} else {
ans = res.score + mid * k;
r = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
