#include <algorithm>
#include <climits>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
template <class segment_tree_template>
struct lazy_segment_tree : public segment_tree_template {
using T = typename segment_tree_template::node_type;
using L = typename segment_tree_template::lazy_type;
using segment_tree_template::node_default_value;
using segment_tree_template::lazy_default_value;
using segment_tree_template::merge;
using segment_tree_template::apply;
int n = 0;
std::vector<T> tree;
std::vector<L> lazy;
void pushdown(int t, int tl, int tr) {
if (lazy[t] == lazy_default_value) return;
int tm = (tl + tr) / 2;
apply(tree[t * 2], lazy[t * 2], lazy[t], tl, tm);
apply(tree[t * 2 + 1], lazy[t * 2 + 1], lazy[t], tm + 1, tr);
lazy[t] = lazy_default_value;
}
void modify_point(int i, long long x, int t, int tl, int tr) {
if (tl == tr) {
tree[t] = T(tl, x);
return;
}
pushdown(t, tl, tr);
int tm = (tl + tr) / 2;
if (i <= tm)
modify_point(i, x, t * 2, tl, tm);
else
modify_point(i, x, t * 2 + 1, tm + 1, tr);
tree[t] = merge(tree[t * 2], tree[t * 2 + 1]);
}
void update_range(int l, int r, L v, int t, int tl, int tr) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
apply(tree[t], lazy[t], v, tl, tr);
return;
}
pushdown(t, tl, tr);
int tm = (tl + tr) / 2;
update_range(l, r, v, t * 2, tl, tm);
update_range(l, r, v, t * 2 + 1, tm + 1, tr);
tree[t] = merge(tree[t * 2], tree[t * 2 + 1]);
}
T query_range(int l, int r, int t, int tl, int tr) {
if (r < tl || tr < l) return node_default_value;
if (l <= tl && tr <= r) return tree[t];
pushdown(t, tl, tr);
int tm = (tl + tr) / 2;
return merge(query_range(l, r, t * 2, tl, tm),
query_range(l, r, t * 2 + 1, tm + 1, tr));
}
public:
lazy_segment_tree() = default;
explicit lazy_segment_tree(int _n) { init(_n); }
void init(int _n) {
n = _n;
tree.assign(4 * n, node_default_value);
lazy.assign(4 * n, lazy_default_value);
}
void modify(int i, long long x) { modify_point(i, x, 1, 0, n - 1); }
void update(int l, int r, L v) { update_range(l, r, v, 1, 0, n - 1); }
T query(int l, int r) { return query_range(l, r, 1, 0, n - 1); }
};
struct range_max_subsequence_sum_range_negate_segment_tree_template {
struct node_type {
long long Mans = 0, Mpre = 0, Msuf = 0;
int Lans = -1, Rans = -1, Bpre = -1, Bsuf = -1;
long long mans = 0, mpre = 0, msuf = 0;
int lans = INT_MAX, rans = INT_MAX, bpre = INT_MAX, bsuf = INT_MAX;
long long sum = 0;
node_type() = default;
node_type(int i, long long x) {
if (x > 0) {
Mans = Mpre = Msuf = x;
Lans = Rans = Bpre = Bsuf = i;
mans = mpre = msuf = 0;
lans = rans = bpre = i - 1;
bsuf = i + 1;
} else {
Mans = Mpre = Msuf = 0;
Lans = Rans = Bpre = i - 1;
Bsuf = i + 1;
mans = mpre = msuf = x;
lans = rans = bpre = bsuf = i;
}
sum = x;
}
friend std::ostream& operator<<(std::ostream& os, const node_type& n) {
return os << '{' << n.Mans << ", " << n.Mpre << ", " << n.Msuf << ", "
<< n.Lans << ", " << n.Rans << ", " << n.Bpre << ", " << n.Bsuf
<< ", " << n.mans << ", " << n.mpre << ", " << n.msuf << ", "
<< n.lans << ", " << n.rans << ", " << n.bpre << ", " << n.bsuf
<< ", " << n.sum << '}';
}
};
using lazy_type = int;
const node_type node_default_value = node_type();
const lazy_type lazy_default_value = 0;
node_type merge(const node_type& a, const node_type& b) {
using namespace std;
node_type ret;
tie(ret.Mans, ret.Lans, ret.Rans) = max(
{make_tuple(a.Mans, a.Lans, a.Rans),
make_tuple(b.Mans, b.Lans, b.Rans),
make_tuple(a.Msuf + b.Mpre, a.Bsuf, b.Bpre)});
tie(ret.Mpre, ret.Bpre) =
max(make_pair(a.Mpre, a.Bpre), make_pair(a.sum + b.Mpre, b.Bpre));
tie(ret.Msuf, ret.Bsuf) =
max(make_pair(a.Msuf + b.sum, a.Bsuf), make_pair(b.Msuf, b.Bsuf));
tie(ret.mans, ret.lans, ret.rans) = min(
{make_tuple(a.mans, a.lans, a.rans),
make_tuple(b.mans, b.lans, b.rans),
make_tuple(a.msuf + b.mpre, a.bsuf, b.bpre)});
tie(ret.mpre, ret.bpre) =
min(make_pair(a.mpre, a.bpre), make_pair(a.sum + b.mpre, b.bpre));
tie(ret.msuf, ret.bsuf) =
min(make_pair(a.msuf + b.sum, a.bsuf), make_pair(b.msuf, b.bsuf));
ret.sum = a.sum + b.sum;
return ret;
}
void apply(node_type& a, lazy_type& b, lazy_type, int, int) {
node_type r;
r.Mans = -a.mans;
r.Mpre = -a.mpre;
r.Msuf = -a.msuf;
r.Lans = a.lans;
r.Rans = a.rans;
r.Bpre = a.bpre;
r.Bsuf = a.bsuf;
r.mans = -a.Mans;
r.mpre = -a.Mpre;
r.msuf = -a.Msuf;
r.lans = a.Lans;
r.rans = a.Rans;
r.bpre = a.Bpre;
r.bsuf = a.Bsuf;
r.sum = -a.sum;
a = r;
b ^= 1;
}
};
using range_max_subsequence_sum_range_negate_segment_tree =
lazy_segment_tree<range_max_subsequence_sum_range_negate_segment_tree_template>;
int main() {
int n, k;
std::cin >> n >> k;
std::vector<long long> a(n);
for (auto& x : a) std::cin >> x;
range_max_subsequence_sum_range_negate_segment_tree t(n);
for (int i = 0; i < n; i++) t.modify(i, a[i]);
long long r = 0;
for (int i = 0; i < k; i++) {
auto q = t.query(0, n - 1);
if (q.Mans <= 0) break;
r += q.Mans;
t.update(q.Lans, q.Rans, 1);
}
std::cout << r << '\n';
}
