#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; }