#include "bits/stdc++.h"
using namespace std;
deque<long long> a, Jaja;
struct Valor{
long long Izquierda, Derecha, Respuesta, Suma;
};
struct Nodo{
long long Mejor;
int i;
long long Propagar;
};
vector<Valor> _rbol;
vector<Nodo> _rbol2;
Valor Neutro;
Nodo Neutro_;
Valor operator+(const Valor& a, const Valor& b){
Valor c;
c.Izquierda = max(a.Izquierda, a.Suma + b.Izquierda);
c.Derecha = max(b.Derecha, a.Derecha + b.Suma);
c.Suma = b.Suma + a.Suma;
c.Respuesta= max(max(a.Respuesta, b.Respuesta), a.Derecha + b.Izquierda);
return c;
}
Nodo operator+(const Nodo& a, const Nodo& b){
Nodo c;
c.Propagar = 0;
if(a.Mejor < b.Mejor){
c.Mejor = a.Mejor;
c.i = a.i;
} else if(a.Mejor > b.Mejor){
c.Mejor = b.Mejor;
c.i = b.i;
} else {
c.Mejor = a.Mejor;
c.i = min(a.i, b.i);
}
return c;
}
void Propagar(int p, bool Seguir){
_rbol2[p].Mejor += _rbol2[p].Propagar;
if(Seguir){
_rbol2[p * 2].Propagar += _rbol2[p].Propagar;
_rbol2[p * 2 + 1].Propagar += _rbol2[p].Propagar;
}
_rbol2[p].Propagar = 0;
}
Nodo Consulta2(int i, int d, int p, int I, int D){
Propagar(p, i != d);
if(i >= I and d <= D) return _rbol2[p];
if(i > D or d < I) return Neutro_;
int P = (i + d) / 2;
return Consulta2(i, P, p * 2, I, D) + Consulta2(P + 1, d, p * 2 + 1, I, D);
}
void Actualizar2(int i, int d, int p, int I, int D, long long v){
Propagar(p, i != d);
if(i >= I and d <= D){
_rbol2[p].Propagar += v;
Propagar(p, i != d);
return;
}
if(i > D or d < I) return;
int P = (i + d) / 2;
Actualizar2(i, P, p * 2, I, D, v);
Actualizar2(P + 1, d, p * 2 + 1, I, D, v);
_rbol2[p] = _rbol2[p * 2] + _rbol2[p * 2 + 1];
}
void Asignar(int p, long long v){
_rbol[p].Izquierda = max(0LL, v);
_rbol[p].Derecha = max(0LL, v);
_rbol[p].Respuesta = max(0LL, v);
_rbol[p].Suma = v;
}
void Crear(int i, int d, int p){
if(i == d){
Asignar(p, a[i]);
Jaja[i] = p;
_rbol2[p].i = i;
_rbol2[p].Mejor = 2222222222222222;
_rbol2[p].Propagar = 0;
return;
}
int P = (i + d) / 2;
Crear(i, P, p * 2);
Crear(P + 1, d, p * 2 + 1);
_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void Actualizar(int p, int o, long long v){
if(p == 0) return;
if(p == o) Asignar(p, v);
else _rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
Actualizar(p / 2, o + 22, -2222);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin>>n>>k;
k--;
Neutro.Suma = 0;
Neutro.Izquierda = 0;
Neutro.Derecha = 0;
Neutro.Respuesta = 0;
Neutro_.i = n - 1;
Neutro_.Mejor = 2222222222222222;
Neutro_.Propagar = -0;
long long r = 0;
for(int i = 0; i < n; i++){
long long v;
cin>>v;
if(v == 0) continue;
if(a.empty()) a.push_back(v);
else if((a.back() / abs(a.back())) == (v / abs(v))) a.back() += v;
else a.push_back(v);
}
while(!a.empty() and a[0] < 0) a.pop_front();
while(!a.empty() and a.back() < 0) a.pop_back();
n = a.size();
if(n == 0){
cout<<0;
return 0;
}
_rbol.assign(n * 4 + 22, Neutro);
_rbol2.assign(n * 4 + 22, Neutro_);
Jaja.assign(n, 0);
Crear(0, n - 1, 1);
long long Respuesta = _rbol[1].Respuesta;
for(int i = 0; i < n; i++){
if(a[i] < 0){
Actualizar(Jaja[i], Jaja[i], 0);
//Actualizar2(0, n - 1, 1, 0, n - 1, a[i]);
Actualizar2(0, n - 1, 1, i, i, -a[i] - Consulta2(0, n - 1, 1, i, i).Mejor);
k--;
if(k == -1){
k = 0;
auto Peor = Consulta2(0, n - 1, 1, 0, n - 1);
Actualizar2(0, n - 1, 1, 0, Peor.i, a[Peor.i]);
Actualizar2(0, n - 1, 1, Peor.i, Peor.i, 2222222222222222 - Consulta2(0, n - 1, 1, Peor.i, Peor.i).Mejor);
//cerr<<i<<" "<<Peor.Mejor<<" "<<Peor.i<<"\n";
Actualizar(Jaja[Peor.i], Jaja[Peor.i], a[Peor.i]);
}
}
Respuesta = max(Respuesta, _rbol[1].Respuesta);
}
cout<<Respuesta;
return 0;
}
