#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const ld pi = atan(1.0L) * 4;
int n, k, a[maxn], res[maxn];
int main() {
// freopen("../input.inp", "r", stdin);
// freopen("output.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int i = 1;
set<pair<int, int>> s;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
// Create initial segments
while (i <= n) {
int val = 0;
int j = i;
while (j <= n && a[i] * a[j] >= 0) val += a[j++];
s.insert({i, val});
i = j;
}
auto it = s.begin();
// Remove negative segments at the beginning
while (!s.empty() && (*it).second < 0) {
s.erase(it);
it = s.begin();
}
// Remove negative segments at the end
if (!s.empty()) {
it = prev(s.end());
while (!s.empty() && (*it).second < 0) {
s.erase(it);
it = prev(s.end());
}
}
int cnt = s.size() / 2 + 1;
if (s.empty()) {
fill(res, res + n + 1, 0);
cout << res[k];
return 0;
} else if (cnt == 1) {
fill(res + 1, res + n + 1, (*s.begin()).second);
cout << res[k];
return 0;
}
// Push segments into priority queue
for (auto i = s.begin(); i != s.end(); i++) {
q.push({abs((*i).second), (*i).first});
}
int cur = cnt;
int sum = 0;
for (auto i : s) {
if (i.second > 0) sum += i.second;
}
fill(res + cnt, res + n + 1, sum);
// Process merging
for (int i = cnt - 1; i >= 1; i--) {
// Remove negative segments from the set
while (!s.empty() && (*s.begin()).second < 0) s.erase(s.begin());
while (!s.empty() && (*prev(s.end())).second < 0) s.erase(prev(s.end()));
// Merge segments to reduce count
while (cur > i) {
if (q.empty()) break; // Safety check
auto p = q.top();
q.pop();
auto it = s.lower_bound({p.second, -mod});
if (it == s.end()) continue;
int id = (*it).first;
// Handle boundary cases
if (it == s.begin()) {
auto nex = next(it);
if (nex == s.end()) continue; // Avoid invalid access
cur -= ((*it).second >= 0) + ((*nex).second >= 0);
sum -= ((*it).second >= 0 ? (*it).second : 0) +
((*nex).second >= 0 ? (*nex).second : 0);
int nw = (*it).second + (*nex).second;
cur += (nw >= 0);
if (nw >= 0) sum += nw;
s.erase(it);
s.erase(nex);
s.insert({id, nw});
q.push({abs(nw), id});
} else if (it == prev(s.end())) {
auto pre = prev(it);
if (pre == s.end()) continue;
cur -= ((*it).second >= 0) + ((*pre).second >= 0);
sum -= ((*it).second >= 0 ? (*it).second : 0) +
((*pre).second >= 0 ? (*pre).second : 0);
int nw = (*it).second + (*pre).second;
cur += (nw >= 0);
if (nw >= 0) sum += nw;
s.erase(it);
s.erase(pre);
s.insert({id, nw});
q.push({abs(nw), id});
} else {
auto pre = prev(it), nex = next(it);
if (pre == s.end() || nex == s.end()) continue;
cur -= ((*pre).second >= 0) + ((*it).second >= 0) + ((*nex).second >= 0);
sum -= ((*pre).second >= 0 ? (*pre).second : 0) +
((*it).second >= 0 ? (*it).second : 0) +
((*nex).second >= 0 ? (*nex).second : 0);
int nw = (*pre).second + (*it).second + (*nex).second;
cur += (nw >= 0);
if (nw >= 0) sum += nw;
s.erase(pre);
s.erase(it);
s.erase(nex);
s.insert({id, nw});
q.push({abs(nw), id});
}
}
res[i] = sum;
}
cout << res[k];
return 0;
}
