#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node {
int val;
int l, r;
bool deleted;
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
if (!(cin >> N >> K)) return 0;
vector<int> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
// 1. Nén các phần tử cùng dấu liên tiếp
vector<int> condensed;
if (N > 0) {
int cur = A[0];
for (int i = 1; i < N; ++i) {
// Gộp số 0 vào phần dương để dễ xử lý
if ((A[i] >= 0 && cur >= 0) || (A[i] < 0 && cur < 0)) {
cur += A[i];
} else {
condensed.push_back(cur);
cur = A[i];
}
}
condensed.push_back(cur);
}
// 2. Loại bỏ các đoạn âm ở đầu và cuối
int start = 0;
while (start < (int)condensed.size() && condensed[start] <= 0) start++;
int end = (int)condensed.size() - 1;
while (end >= start && condensed[end] <= 0) end--;
if (start > end) { // Không có đoạn dương nào
cout << 0 << endl;
return 0;
}
vector<int> s;
for (int i = start; i <= end; ++i) s.push_back(condensed[i]);
// 3. Tính số đoạn dương hiện có và tổng ban đầu
int n = s.size();
int m = 0;
int current_sum = 0;
for (int x : s) {
if (x > 0) { m++; current_sum += x; }
}
if (m <= K) {
cout << current_sum << endl;
return 0;
}
// 4. Tham lam sử dụng Priority Queue và Danh sách liên kết
vector<Node> nodes(n);
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < n; ++i) {
nodes[i] = {s[i], i - 1, i + 1, false};
pq.push({abs(s[i]), i});
}
int needed_reductions = m - K;
while (needed_reductions > 0) {
pii top = pq.top(); pq.pop();
int i = top.second;
if (nodes[i].deleted) continue;
// Xử lý đoạn âm ở biên phát sinh trong quá trình gộp
if (nodes[i].val <= 0 && (nodes[i].l == -1 || nodes[i].r == n)) {
nodes[i].deleted = true;
if (nodes[i].l != -1) nodes[nodes[i].l].r = nodes[i].r;
if (nodes[i].r != n) nodes[nodes[i].r].l = nodes[i].l;
continue;
}
current_sum -= abs(nodes[i].val);
needed_reductions--;
int L = nodes[i].l;
int R = nodes[i].r;
if (L == -1 || R == n) {
// Xóa đoạn dương ở biên và đoạn âm kế cạnh nó
nodes[i].deleted = true;
int neighbor = (L == -1) ? R : L;
if (neighbor != -1 && neighbor != n) {
nodes[neighbor].deleted = true;
int other = (L == -1) ? nodes[neighbor].r : nodes[neighbor].l;
if (other != -1 && other != n) {
if (L == -1) nodes[other].l = -1;
else nodes[other].r = n;
}
}
} else {
// Gộp 3 đoạn L, i, R thành 1 đoạn mới
nodes[i].val += nodes[L].val + nodes[R].val;
nodes[L].deleted = true;
nodes[R].deleted = true;
nodes[i].l = nodes[L].l;
if (nodes[i].l != -1) nodes[nodes[i].l].r = i;
nodes[i].r = nodes[R].r;
if (nodes[i].r != n) nodes[nodes[i].r].l = i;
pq.push({abs(nodes[i].val), i});
}
}
cout << current_sum << endl;
return 0;
}
