#include<bits/stdc++.h>
using namespace std;
struct T {
long long cost;
int l, r;
T(long long cost, int l, int r) : cost(cost), l(l), r(r) {
}
bool operator < (const T& other) const {
return cost < other.cost;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("test.inp", "r", stdin);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<T> t;
vector<int> prev(n, -1);
vector<int> nxt(n, -1);
vector<long long> res(n);
for (int i = 0; i < n; i++) {
int j = i + 1;
long long now = a[i];
while (j < n && (a[i] >= 0) == (a[j] >= 0)) now += a[j++];
if (i == 0 && now < 0) {
i = j - 1;
continue;
}
if (j == n && now < 0) break;
t.push_back(T(now, i, j));
if (j < n) {
nxt[i] = j;
prev[j] = i;
}
res[i] = -abs(now);
i = j - 1;
}
if (n == 1) {
cout << max(a[0], 0);
return 0;
}
priority_queue<T> pq;
long long ans = 0;
for (int i = 0; i < (int) t.size(); i++) {
if (t[i].cost > 0) ans += t[i].cost, --k;
pq.push(T{-abs(t[i].cost), t[i].l, t[i].r});
// cout << t[i].cost <<" " << t[i].l <<" " << t[i].r << endl;
}
cout << k << " " << nxt[72] << endl;
vector<int> flag(n + 1);
while (!pq.empty() && k < 0) {
/*
a-x-b mn
a + b -> a + b + mn - x
*/
auto x = pq.top(); pq.pop();
long long cost = x.cost;
int l = x.l, r = x.r;
int ll = prev[l], rr = nxt[r];
// for (int i = 0; i < n; i++) cout << res[i] <<" "; cout << endl;
if (res[l] != cost || flag[l] || flag[r]) continue;
// cout << cost <<" " << l <<" " << r << endl;
k++;
ans += cost;
flag[l] = flag[r] = true;
if (ll == -1) {
long long val = res[r] - cost;
res[l] = val;
pq.push(T{val, l, rr});
continue;
}
if (rr == -1) {
long long val = res[ll] - cost;
res[ll] = val;
pq.push(T{val, ll, r});
continue;
}
long long val = res[ll] + res[r] - cost;
res[ll] = val;
pq.push(T{val, ll, rr});
}
cout << ans;
}
