#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'
vector<long long> feast;
class divandqonqtree{
private:
divandqonqtree *lfttree, *rgttree;
struct prefixdata{
long long int maximumrightmostsum = 0;
int leftind = 0;
long long int maximumsubarraysum = 0;
int kanadeleft = 0;
int kanaderight = 0;
};
struct sufixdata{
long long int maximumleftmostsum = 0;
int rightind = 0;
long long int maximumsubarraysum = 0;
int kanadeleft = 0;
int kanaderight = 0;
};
vector<prefixdata> prefix;
vector<sufixdata> sufix;
int l, m, r;
long long deg;
public:
void init(int gl, int gr){
l = gl;
r = gr;
m = (l + r) >> 1;
if (gl == gr){
deg = feast[l];
return;
}
if (l < m){
lfttree = new divandqonqtree;
lfttree->init(l, m - 1);
}
if (m < r){
rgttree = new divandqonqtree;
rgttree->init(m + 1, r);
}
long long int sum = 0, kanade = 0, kl = m;
prefix.resize(m - l + 1);
sufix.resize(r - m + 1);
for (int i = m; i <= r; i++){
sum += feast[i];
kanade += feast[i];
if (kanade < 0){
kanade = 0;
kl = i + 1;
}
if (i == m){
sufix[0].maximumleftmostsum = max(0LL, sum);
sufix[0].maximumsubarraysum = kanade;
continue;
}
if (sufix[i - m - 1].maximumleftmostsum > sum){
sufix[i - m].maximumleftmostsum = sufix[i - m - 1].maximumleftmostsum;
sufix[i - m].rightind = sufix[i - m - 1].rightind;
}else{
sufix[i - m].maximumleftmostsum = sum;
sufix[i - m].rightind = i;
}
if (sufix[i - m - 1].maximumsubarraysum > kanade){
sufix[i - m].maximumsubarraysum = sufix[i - m - 1].maximumsubarraysum;
sufix[i - m].kanadeleft = sufix[i - m - 1].kanadeleft;
sufix[i - m].kanaderight = sufix[i - m - 1].kanaderight;
}else{
sufix[i - m].maximumsubarraysum = kanade;
sufix[i - m].kanadeleft = kl;
sufix[i - m].kanaderight = i;
}
}
kl = m;
sum = 0;
kanade = 0;
for (int i = m; i >= l; i--){
if (i == m){
prefix[0].maximumrightmostsum = sum;
prefix[0].maximumsubarraysum = kanade;
continue;
}
sum += feast[i];
kanade += feast[i];
if (kanade < 0){
kanade = 0;
kl = i - 1;
}
if (prefix[m - i - 1].maximumrightmostsum > sum){
prefix[m - i].maximumrightmostsum = prefix[m - i - 1].maximumrightmostsum;
prefix[m - i].leftind = prefix[m - i - 1].leftind;
}else{
prefix[m - i].maximumrightmostsum = sum;
prefix[m - i].leftind = i;
}
if (prefix[m - i - 1].maximumsubarraysum > kanade){
prefix[m - i].maximumsubarraysum = prefix[m - i - 1].maximumsubarraysum;
prefix[m - i].kanadeleft = prefix[m - i - 1].kanadeleft;
prefix[m - i].kanaderight = prefix[m - i - 1].kanaderight;
}else{
prefix[m - i].maximumsubarraysum = kanade;
prefix[m - i].kanadeleft = i;
prefix[m - i].kanaderight = kl;
}
}
};
array<long long, 3> query(int ql, int qr){
if (ql > qr)
return { -1, -1, -1 };
if (qr < m){
return lfttree->query(ql, qr);
}
if (ql > m){
return rgttree->query(ql, qr);
}
if (l == r){
return { deg, l, r };
}
long long mx = max(max(prefix[m - ql].maximumsubarraysum, sufix[qr - m].maximumsubarraysum), prefix[m - ql].maximumrightmostsum + sufix[qr - m].maximumleftmostsum);
if (mx == prefix[m - ql].maximumsubarraysum)
return { mx, prefix[m - ql].kanadeleft, prefix[m - ql].kanaderight };
if (mx == sufix[qr - m].maximumsubarraysum)
return { mx, sufix[qr - m].kanadeleft, sufix[qr - m].kanaderight };
// if (mx == prefix[m - ql].maximumrightmostsum + sufix[qr - m].maximumleftmostsum)
return { mx, prefix[m - ql].leftind, sufix[qr - m].rightind};
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
cin >> N >> K;
vector<long long> original(N);
multiset<long long> sm;
for (int i = 0; i < N; i++){
cin >> original[i];
sm.insert(-original[i]);
}
long long int sum = 0;
for (int o = 0; o < K; o++){
if (*sm.begin() < 0)
sum += -*sm.begin();
sm.erase(sm.begin());
}
if (*sm.begin() >= 0){
cout << sum;
return 0;
}
for (int i = 0; i < N; i++){
long long a = original[i];
if (a == 0)
continue;
if (feast.size() == 0 && a > 0){
feast.push_back(a);
continue;
}
if (feast.back() * a > 0)
feast.back() += a;
else
feast.push_back(a);
}
if (feast[feast.size() - 1] < 0)
feast.pop_back();
divandqonqtree normal, inverse;
normal.init(0, feast.size() - 1);
for (int i = 0; i < feast.size(); i++) feast[i] *= -1;
inverse.init(0, feast.size() - 1);
priority_queue<array<long long, 6>> prt;
auto u = normal.query(0, feast.size() - 1);
prt.push({ u[0], 0LL, (long long)feast.size() - 1LL, (long long)true, u[1], u[2] });
long long int ret = 0;
for (int i = 0; i < K; i++){
auto fr = prt.top();
prt.pop();
ret += fr[0];
if (fr[3]){
u = normal.query(fr[1], fr[4] - 1);
prt.push({ u[0], fr[0], fr[4] - 1, true, u[1], u[2] });
u = normal.query(fr[5] + 1, fr[2]);
prt.push({ u[0], fr[5] + 1, fr[1], true, u[1], u[2] });
u = inverse.query(fr[4], fr[5]);
prt.push({ u[0], fr[4], fr[5], false, u[1], u[2] });
}else{
u = inverse.query(fr[1], fr[4] - 1);
prt.push({ u[0], fr[0], fr[4] - 1, false, u[1], u[2] });
u = inverse.query(fr[5] + 1, fr[2]);
prt.push({ u[0], fr[5] + 1, fr[1], false, u[1], u[2] });
u = normal.query(fr[4], fr[5]);
prt.push({ u[0], fr[4], fr[5], true, u[1], u[2] });
}
}
cout << ret;
return 0;
}
