rt

#include<cstdio>
#include<cmath>
#include<queue>
#define fi first
#define se second
#define mkp(a,b) make_pair((a),(b))
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+5;
priority_queue<pii,vector<pii>,greater<pii> > Posit,Negat;
int vis[N],m,n,A[N],B[N],ans,cnt;
struct Node{
	int a[N],l[N],r[N];
	void build(int* x,int len){
		for(int i=1;i<=len;i++){
			l[i]=i-1;r[i]=i+1;
			a[i]=x[i];
		}
		r[0]=1;
		l[len+1]=len;r[len+1]=len+1;
	}
	pii link(int x){
		int ll=l[x],rr=r[x];
		r[l[ll]]=l[r[rr]]=x;
		l[x]=l[ll];r[x]=r[rr];
		a[x]=a[x]+a[ll]+a[rr];
		return mkp(abs(a[x]),x);
	}
	void eraze(int x){
		int ll=l[x],rr=r[r[x]];
		r[ll]=rr;l[rr]=ll;
	}
}lb;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&A[i]);
	}
	int K1=1,K2=0;
	while(K1<=n){
		int tot=0;
		if(A[K1]>0){
			while(A[K1]>=0&&K1<=n){
				tot+=A[K1];
				K1++;
			}
		}else{
			while(A[K1]<=0&&K1<=n){
				tot+=A[K1];
				K1++;
			}
		}
		B[++K2]=tot;
		if(tot>0){
			Posit.push(mkp(tot,K2));
			ans+=tot;
			cnt+=1;
		}else if(K1<=n&&K2!=1){
			Negat.push(mkp(-tot,K2));
		}
		if(K1>n&&tot<0) K2--;
		if(K2==1&&tot<0) K2--;
	}
	lb.build(B,K2);
	while(cnt>m){
		while(!Posit.empty()&&vis[Posit.top().se]) Posit.pop();
		while(!Negat.empty()&&vis[Negat.top().se]) Negat.pop();
		if(Posit.top().fi<=Negat.top().fi){
			int w=Posit.top().se;
			ans-=Posit.top().fi;
			Posit.pop();
			if(lb.l[w]==0){
				vis[w]=vis[lb.r[w]]=1;
				lb.eraze(w);
			}else{
				vis[lb.l[w]]=vis[lb.r[w]]=1;
				Negat.push(lb.link(w));				
			}
			cnt--;
		}else{
			int w=Negat.top().se;
			ans-=Negat.top().fi;
			Negat.pop();
			vis[lb.l[w]]=vis[lb.r[w]]=1;
			Posit.push(lb.link(w));
			cnt--;
		}
	}
	printf("%lld",ans);
}