#include<bits/stdc++.h>
using namespace std;
const int nmax = 3e5+5;
int A[nmax];
struct allin {
int sum;
int maxsum;
int preff;
int suff;
};
allin segtree[4*nmax];
void build(int idx, int low, int high) {
if(low==high) {
segtree[idx].sum = A[low];
segtree[idx].maxsum = A[low];
segtree[idx].preff = A[low];
segtree[idx].suff = A[low];
return;
}
int mid = (low+high)/2;
build(2*idx,low,mid);
build(2*idx+1,mid+1,high);
segtree[idx].sum = segtree[2*idx].sum + segtree[2*idx+1].sum;
segtree[idx].maxsum = max(max(segtree[2*idx].maxsum, segtree[2*idx+1].maxsum), segtree[2*idx].suff + segtree[2*idx+1].preff);
segtree[idx].preff = max(segtree[2*idx].preff, segtree[2*idx].sum+segtree[2*idx+1].preff);
segtree[idx].suff = max(segtree[2*idx+1].suff, segtree[2*idx+1].sum + segtree[2*idx].suff);
}
allin query(int idx, int low, int high, int l, int r) {
if(low>=l && high<=r) {
return segtree[idx];
}
int mid = (low+high)/2;
if(r<=mid) {
return query(2*idx, low, mid, l, r);
} else
if(l>mid) {
return query(2*idx+1, mid+1, high, l, r);
} else {
allin left = query(2*idx, low, mid, l, r);
allin right = query(2*idx+1, mid+1, high, l, r);
allin merge;
merge.sum = left.sum + right.sum;
merge.maxsum = max(max(left.maxsum, right.maxsum), left.suff+right.preff);
merge.preff = max(left.preff, left.sum+right.preff);
merge.suff = max(right.suff, right.sum+left.suff);
return merge;
}
}
int main() {
int N,K;
cin >> N >> K;
bool subs1 = true;
long long summ=0;
for(int i=1; i<=N; i++) {
cin >> A[i];
if(A[i]<0) subs1=false;
summ+=A[i];
}
build(1,1,N);
if(subs1) {
cout << summ << endl;
return 0;
}
if(K==1) {
allin ans = query(1,1,N,1,N);
cout << ans.maxsum << endl;
return 0;
}
int posneg;
for(int i=1; i<=N; i++) {
if(A[i]<0) {
posneg = i;
break;
}
}
summ=0;
if(K>=2) {
for(int i=1; i<posneg; i++) {
summ+=A[i];
}
for(int i=posneg+1; i<=N; i++) {
summ+=A[i];
}
cout << summ << endl;
return 0;
}
return 0;
}
