#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 (C)
pair<int, int> solve_unconstrained(int n, int C, 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.
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 C tax, increment count)
pair<int, int> start_new = {dp0.first + a[i] - C, 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) {
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) {
ans = res.first + k * mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
// Pseudo Fucken Code!
void run_case(int tc) {
int n, k;
cin >> n >> k;
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;
}
