#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <climits>
using namespace std;
typedef long long ll;
tuple<ll, int, int> solve(ll lam, vector<ll> &a) {
int n = a.size();
if (n == 0)
return make_tuple(0, 0, 0);
ll dp0_val = 0;
int dp0_min = 0, dp0_max = 0;
ll dp1_val = a[0] - lam;
int dp1_min = 1, dp1_max = 1;
for (int i = 1; i < n; i++) {
ll prev0_val = dp0_val;
ll prev1_val = dp1_val;
int prev0_min = dp0_min, prev0_max = dp0_max;
int prev1_min = dp1_min, prev1_max = dp1_max;
if (prev0_val > prev1_val) {
dp0_val = prev0_val;
dp0_min = prev0_min;
dp0_max = prev0_max;
} else if (prev0_val < prev1_val) {
dp0_val = prev1_val;
dp0_min = prev1_min;
dp0_max = prev1_max;
} else {
dp0_val = prev0_val;
dp0_min = min(prev0_min, prev1_min);
dp0_max = max(prev0_max, prev1_max);
}
ll option1_val = prev0_val + a[i] - lam;
int option1_min = prev0_min + 1;
int option1_max = prev0_max + 1;
ll option2_val = prev1_val + a[i];
int option2_min = prev1_min;
int option2_max = prev1_max;
if (option1_val > option2_val) {
dp1_val = option1_val;
dp1_min = option1_min;
dp1_max = option1_max;
} else if (option1_val < option2_val) {
dp1_val = option2_val;
dp1_min = option2_min;
dp1_max = option2_max;
} else {
dp1_val = option1_val;
dp1_min = min(option1_min, option2_min);
dp1_max = max(option1_max, option2_max);
}
}
ll res_val;
int res_min, res_max;
if (dp0_val > dp1_val) {
res_val = dp0_val;
res_min = dp0_min;
res_max = dp0_max;
} else if (dp0_val < dp1_val) {
res_val = dp1_val;
res_min = dp1_min;
res_max = dp1_max;
} else {
res_val = dp0_val;
res_min = min(dp0_min, dp1_min);
res_max = max(dp0_max, dp1_max);
}
return make_tuple(res_val, res_min, res_max);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<ll> A(N);
int count_positive = 0;
for (int i = 0; i < N; i++) {
cin >> A[i];
if (A[i] > 0)
count_positive++;
}
int K0 = min(K, count_positive);
if (K0 == 0) {
cout << 0 << endl;
return 0;
}
ll low = -3e14;
ll high = 3e14;
ll ans_seg = -1e18;
bool found = false;
while (low <= high) {
ll lam = (low + high) / 2;
auto [val, cmin, cmax] = solve(lam, A);
if (cmax < K0) {
high = lam - 1;
} else if (cmin > K0) {
low = lam + 1;
} else {
ans_seg = val + lam * K0;
found = true;
break;
}
}
if (found) {
ll ans = max(0LL, ans_seg);
cout << ans << endl;
} else {
auto [val_low, cmin_low, cmax_low] = solve(low, A);
ll candidate_low = -1e18;
if (cmin_low <= K0 && K0 <= cmax_low) {
candidate_low = val_low + low * K0;
} else {
int k1 = max(cmin_low, 0);
int k2 = min(cmax_low, K0);
candidate_low = max(val_low + low * k1, val_low + low * k2);
}
auto [val_high, cmin_high, cmax_high] = solve(high, A);
ll candidate_high = -1e18;
if (cmin_high <= K0 && K0 <= cmax_high) {
candidate_high = val_high + high * K0;
} else {
int k1 = max(cmin_high, 0);
int k2 = min(cmax_high, K0);
candidate_high = max(val_high + high * k1, val_high + high * k2);
}
ll ans = max(0LL, max(candidate_low, candidate_high));
cout << ans << endl;
}
return 0;
}
