#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -(ll)9e18;
struct Node {
int l, r;
ll sum;
ll pref; int prefL, prefR;
ll suf; int sufL, sufR;
ll best; int bestL, bestR;
bool lazy; // assign to NEG
Node() {
l = r = 0;
sum = pref = suf = best = NEG;
prefL = prefR = sufL = sufR = bestL = bestR = -1;
lazy = false;
}
};
int N, K;
vector<ll> a;
vector<Node> seg;
Node make_leaf(int idx, ll val) {
Node nd;
nd.l = nd.r = idx;
nd.sum = val;
nd.pref = val; nd.prefL = nd.prefR = idx;
nd.suf = val; nd.sufL = nd.sufR = idx;
nd.best = val; nd.bestL = nd.bestR = idx;
nd.lazy = false;
return nd;
}
Node combine(const Node &L, const Node &R) {
if (L.l==0) return R;
if (R.l==0) return L;
Node res;
res.l = L.l; res.r = R.r;
res.sum = L.sum + R.sum;
// prefix
ll leftPref = L.pref;
ll crossPref = (L.sum==NEG || R.pref==NEG) ? NEG : L.sum + R.pref;
if (leftPref >= crossPref) {
res.pref = leftPref;
res.prefL = L.prefL; res.prefR = L.prefR;
} else {
res.pref = crossPref;
res.prefL = L.l; res.prefR = R.prefR;
}
// suffix
ll rightSuf = R.suf;
ll crossSuf = (R.sum==NEG || L.suf==NEG) ? NEG : R.sum + L.suf;
if (rightSuf >= crossSuf) {
res.suf = rightSuf;
res.sufL = R.sufL; res.sufR = R.sufR;
} else {
res.suf = crossSuf;
res.sufL = L.sufL; res.sufR = R.r;
}
// best
res.best = L.best; res.bestL = L.bestL; res.bestR = L.bestR;
if (R.best > res.best) {
res.best = R.best; res.bestL = R.bestL; res.bestR = R.bestR;
}
if (L.suf != NEG && R.pref != NEG) {
ll cross = L.suf + R.pref;
if (cross > res.best) {
res.best = cross;
res.bestL = L.sufL;
res.bestR = R.prefR;
}
}
res.lazy = false;
return res;
}
void build(int p, int l, int r) {
if ((int)seg.size() <= p) seg.resize(p+1);
seg[p].l = l; seg[p].r = r;
seg[p].lazy = false;
if (l == r) {
seg[p] = make_leaf(l, a[l]);
return;
}
int m = (l + r) >> 1;
build(p<<1, l, m);
build(p<<1|1, m+1, r);
seg[p] = combine(seg[p<<1], seg[p<<1|1]);
}
void apply_assign_neg(int p) {
seg[p].sum = NEG * (seg[p].r - seg[p].l + 1);
seg[p].pref = seg[p].suf = seg[p].best = NEG;
seg[p].prefL = seg[p].prefR = seg[p].sufL = seg[p].sufR = seg[p].bestL = seg[p].bestR = -1;
seg[p].lazy = true;
}
void push(int p) {
if (!seg[p].lazy || seg[p].l == seg[p].r) return;
apply_assign_neg(p<<1);
apply_assign_neg(p<<1|1);
seg[p].lazy = false;
}
void update_range_assign_neg(int p, int l, int r) {
if (r < seg[p].l || seg[p].r < l) return;
if (l <= seg[p].l && seg[p].r <= r) {
apply_assign_neg(p);
return;
}
push(p);
update_range_assign_neg(p<<1, l, r);
update_range_assign_neg(p<<1|1, l, r);
seg[p] = combine(seg[p<<1], seg[p<<1|1]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> N >> K)) return 0;
a.assign(N+1, 0);
for (int i = 1; i <= N; ++i) cin >> a[i];
seg.assign(4*(N+5), Node());
build(1,1,N);
ll ans = 0;
for (int t = 0; t < K; ++t) {
ll best = seg[1].best;
if (best <= 0) break;
int L = seg[1].bestL;
int R = seg[1].bestR;
ans += best;
update_range_assign_neg(1, L, R);
}
cout << ans << '\n';
return 0;
}
