// Programmer: Shadow1
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!
#define i64 int64_t
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define prq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
// Feast trick
// What's it even called lol
void solve() {
int n, k;
cin >> n >> k;
deque<int> a(n+1);
for(int i=1; i<=n; ++i) {
cin >> a[i];
}
while(!a.empty() && a.front() <= 0) a.pop_front(); // remove prefix of negs
while(!a.empty() && a.back() <= 0) a.pop_back(); // remove suffix of negs
bool pos = true;
vector<int> c = {0};
for(int i=0; i<sz(a); ++i) { // merge pos and negs
if((pos && a[i] >= 0) || (!pos && a[i] < 0))
c.back() += a[i];
else {
c.push_back(a[i]);
pos = !pos;
}
}
n = sz(c);
// output_vector(c);
int cnt = (n+1) / 2;
int ans = 0;
vector<pii> range(n);
vector<int> p(n);
p[0] = c[0];
for(int i=0; i<n; ++i) {
range[i] = {i, i};
}
for(int i=1; i<n; ++i)
p[i] = p[i-1] + c[i];
auto cmp = [](pair<int, pii> &a, pair<int, pii> &b) {
if(abs(a.fir) == abs(b.fir))
return a.sec < b.sec;
return abs(a.fir) > abs(b.fir);
};
priority_queue<pair<int, pii>, vector<pair<int, pii>>, decltype(cmp)> pq(cmp);
for(int i=0; i<n; i++) {
pq.push({c[i], {i, i}});
}
map<int, bool> vis[n];
int s = 0, e = n-1;
while(!pq.empty() && cnt > k) {
int t = pq.top().fir;
int l = pq.top().sec.fir;
int r = pq.top().sec.sec;
pq.pop();
if(vis[l][r]) continue;
vis[l][r] = true;
// show(t);
if(l > s) { // combine left
int ll = range[l-1].fir;
int rr = range[l-1].sec;
int d = 0;
d += p[rr];
if(ll > 0) d -= p[ll-1];
vis[ll][rr] = true;
l = ll;
t += d;
}
if(r < e) { // combine right
int ll = range[r+1].fir;
int rr = range[r+1].sec;
int d = 0;
d += p[rr];
if(ll > 0) d -= p[ll-1];
vis[ll][rr] = true;
r = rr;
t += d;
}
range[l].fir = range[r].fir = l;
range[l].sec = range[r].sec = r;
if(t <= 0 && l == s)
s = l;
else if(t <= 0 && r == e)
e = r;
else
pq.push({t, {l, r}});
cnt--;
}
while(!pq.empty()) {
if(pq.top().fir > 0 && !vis[pq.top().sec.fir][pq.top().sec.sec]) {
ans += pq.top().fir;
// show(pq.top().fir);
}
pq.pop();
}
cout << ans << '\n';
}
// CHECK YOUR OVERFLOWS!!!!
signed main() {
// freopen("output.txt", "w", stdout);
// freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
// cin >> T;
for(int tc = 1; tc <= T; ++tc) {
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
