#define _CRT_SECURE_NO_WARNINGS
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int sz = 3e5 + 5;
int k, n;
ll a[sz];
map<int, pair<ll, bool>> arr; //pos, val, isNeg
set<pair<ll, pair<bool, int>>> q;//val, pos, isNeg
inline pair<int, pair<ll, bool>> qToArr(pair<ll, pair<bool, int> > x) {
return { x.second.second, {x.first,x.second.first} };
}
inline pair<ll, pair<bool, int>> arrToQ(pair<int, pair<ll, bool>> x) {
return { x.second.first,{x.second.second,x.first} };
}
bool fix(vector<ll>& v) {
if (v.back() < 0)v.pop_back();
if (v.empty())return 0;
reverse(v.begin(), v.end());
if (v.back() < 0)v.pop_back();
if (v.empty())return 0;
return 1;
}
void removeFromDS(pair<ll, pair<bool, int>> x) {
auto y = arr.find(x.second.second), yp = y, ym = y;
yp++;
ym--;
if (x.second.first) {
ll nval = yp->second.first + ym->second.first - x.first;
q.erase(arrToQ(*yp));
q.erase(arrToQ(*ym));
q.erase(x);
q.insert({ nval,{0,x.second.second} });
arr[x.second.second] = { nval, 0 };
arr.erase(yp);
arr.erase(ym);
}
else {
if (ym == arr.end()) {
q.erase(arrToQ(*yp));
q.erase(x);
arr.erase(yp);
arr.erase(qToArr(x).first);
}
else if (yp == arr.end()) {
q.erase(arrToQ(*ym));
q.erase(x);
arr.erase(ym);
arr.erase(qToArr(x).first);
}
else {
ll nval = yp->second.first + ym->second.first - x.first;
q.erase(arrToQ(*yp));
q.erase(arrToQ(*ym));
q.erase(x);
q.insert({ nval,{1,x.second.second} });
arr[x.second.second] = { nval, 1 };
arr.erase(yp);
arr.erase(ym);
}
}
}
ll solve(vector<ll> v) {
if (!fix(v))return 0;
ll tot = 0;
int vsz = v.size();
for (int i = 0; i < vsz; i += 2) {
tot += v[i];
}
foru(i, 0, vsz) {
arr[i] = { abs(v[i]),i & 1 }; q.insert({ abs(v[i]),{i & 1,i} });
}
int cur = vsz / 2 + 1;
while (cur > k) {
auto x = *q.begin();
tot -= x.first;
removeFromDS(x);
cur--;
}
return tot;
}
int main() {
fast;
//freopen("input.txt", "r", stdin);
//freopen("outbad.txt", "w", stdout);
int t=1;
//cin >> t;
while (t--) {
arr.clear();
q.clear();
cin >> n >> k;
foru(i, 0, n)cin >> a[i];
ll ts = 0;
bool f = 1, pos = 0;
vector<ll> v;
foru(i, 0, n) {
if (f) {
pos = (a[i] >= 0);
ts += a[i];
f = 0;
}
else {
if ((a[i] >= 0) != (a[i - 1] >= 0)) {
pos = !pos;
v.pb(ts);
ts = a[i];
}
else ts += a[i];
}
}
v.pb(ts);
cout << solve(v) << '\n';
}
return 0;
}
