#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>
ll n, m, k;
ll t;
ll a[dim];
ll dp[dim];
int main() {
ll u, w,q, v, y;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k;
set<pll> sml;
set<pll> s;
ll sm=0;
ll fl=1;
ll c=0;
for(int i=1; i<=n; i++) {
cin >> a[i];
if (fl && a[i] >= 0) {
sm += a[i];
} else if (fl == 0 && a[i] < 0) {
sm += a[i];
} else {
c++;
s.insert({c, sm});
sm=0;
fl = 1 - fl;
sm += a[i];
}
}
c++;
s.insert({c, sm});
while(s.size()>0 && (*s.begin()).se<=0){
s.erase(s.begin());
}
while(s.size()>0 && (*s.rbegin()).se<=0){
s.erase(*s.rbegin());
}
m=s.size();
m=(m+1)/2;
ll ans=0;
for(auto x: s){
ll p1=x.fi;
ll p2=x.se;
// cout<<p1<<" "<<p2<<endl;
if(p2>0)ans+=x.se;
sml.insert({abs(p2), p1});
}
// cout<<ans<<endl;
if(m<=k){
cout<<ans<<endl;
return 0;
}
else m-=k;
while(m>0){
m--;
while(s.size()>0 && (*s.begin()).se<=0){
pll x=(*s.begin());
s.erase(s.begin());
ll p1=x.fi;
ll p2=x.se;
sml.erase({abs(p2), p1});
}
while(s.size()>0 && (*s.rbegin()).se<=0){
pll x=(*s.rbegin());
s.erase(*s.rbegin());
ll p1=x.fi;
ll p2=x.se;
sml.erase({abs(p2), p1});
}
pll cur=(*sml.begin());
sml.erase(cur);
ans-=cur.fi;
//cout<<cur.fi<<" "<<cur.se<<endl;
ll cnt=0;
auto it1=s.lower_bound({cur.se, -inf});
cnt+=(*it1).se;
if(it1==s.begin() || it1==(--s.end())){
s.erase(it1);
continue;
}
s.erase(it1);
it1=s.lower_bound({cur.se, -inf});
auto it2=s.lower_bound({cur.se+1, 0});
if(it1!=s.begin()){
it1--;
pll p1=(*it1);
s.erase(it1);
cnt+=p1.se;
// cout<<" merge "<<p1.fi<<" "<<p1.se<<endl;
sml.erase({abs(p1.se), p1.fi});
}
if(it2!=s.end()){
pll p2=(*it2);
s.erase(it2);
cnt+=p2.se;
// cout<<" merge "<<p2.fi<<" "<<p2.se<<endl;
sml.erase({abs(p2.se), p2.fi});
}
//cout<<cnt<<"--"<<endl;
sml.insert({abs(cnt), cur.se});
s.insert({cur.se, cnt});
}
cout<<ans<<endl;
return 0;
}
