#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define el "\n"
const int INF = 1e18;
// Returns {max_profit, segments_used} for a given tax (lambda)
pair<int, int> solve_unconstrained(int n, int lambda, const vector<int>& a) {
// dp0: Max profit up to index i, currently NOT in a segment
pair<int, int> dp0 = {0, 0};
// dp1: Max profit up to index i, currently IN a segment
pair<int, int> dp1 = {-INF, 0};
for (int i = 1; i <= n; i++) {
// Option 1: End the previous segment or stay out of a segment.
// std::max maximizes profit first, then segments used on ties.
pair<int, int> next_dp0 = max(dp0, dp1);
// Option 2: Be inside a segment. We have two ways to do this:
// a) Extend the current open segment (no new tax, no new segment count)
pair<int, int> extend = {dp1.first + a[i], dp1.second};
// b) Start a brand new segment (pay the lambda tax, increment count)
pair<int, int> start_new = {dp0.first + a[i] - lambda, dp0.second + 1};
pair<int, int> next_dp1 = max(extend, start_new);
dp0 = next_dp0;
dp1 = next_dp1;
}
// Return the best possible outcome at the end of the array
return max(dp0, dp1);
}
int aliens_trick(int n, int k, const vector<int>& a) {
// Tax bounds: 0 (take everything > 0) to 1e15 (take nothing).
// Kept high bound safe from INF to prevent overflow when adding.
int low = 0, high = 1e15, ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
pair<int, int> res = solve_unconstrained(n, mid, a);
if (res.second >= k) {
// Picked too many or exactly K items. The tax is too low/just right.
// Record the actual answer (profit + the tax we paid for exactly K items)
// Note: Even if res.second > k, the mathematical properties of the convex hull
// guarantee this specific equation still calculates the exact correct answer for K.
ans = res.first + k * mid;
low = mid + 1; // Try to increase tax to pick fewer items
} else {
// Picked too few items. Tax is too high.
high = mid - 1;
}
}
return ans;
}
// Pseudo Fucken Code!
void run_case(int tc) {
int n, k;
if (!(cin >> n >> k)) return;
// 1-based indexing to match your template logic
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cout << aliens_trick(n, k, a) << el;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _t = 1;
// cin >> _t;
for (int i = 1; i <= _t; i++) {
run_case(i);
}
return 0;
}
