#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val; // valor del elemento
int idx; // índice en el array original (inicio del bloque)
int l, r; // índices de bloques vecinos (-1 si no existe)
// Para ordenar por valor ascendente en el priority queue
bool operator<(const Node& other) const {
return val > other.val; // Invertido para min-heap
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
if (!(cin >> N >> K)) return 0;
vector<long long> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
// ===== FASE 1: Preprocesar =====
// Combinar elementos del mismo signo
vector<long long> B; // Array preprocesado
vector<int> startIdx; // Índice de inicio de cada bloque en A original
for (int i = 0; i < N; i++) {
if (B.empty() || (A[i] >= 0 && B.back() < 0) || (A[i] < 0 && B.back() >= 0)) {
B.push_back(A[i]);
startIdx.push_back(i);
} else {
B.back() += A[i];
}
}
// Eliminar negativos de los extremos
while (!B.empty() && B.front() < 0) {
B.erase(B.begin());
startIdx.erase(startIdx.begin());
}
while (!B.empty() && B.back() < 0) {
B.pop_back();
startIdx.pop_back();
}
int M = B.size();
if (M == 0) {
cout << 0 << "\n";
return 0;
}
// ===== FASE 2: Verificar si hay más positivos que K =====
// Contar positivos
int posCount = 0;
for (int i = 0; i < M; i++) {
if (B[i] > 0) posCount++;
}
// Si hay <= K positivos, sumar todos
if (posCount <= K) {
long long ans = 0;
for (int i = 0; i < M; i++) {
if (B[i] > 0) ans += B[i];
}
cout << ans << "\n";
return 0;
}
// ===== FASE 3: Eliminar K menores positivos =====
// Usar priority queue para elementos positivos
priority_queue<Node> pq;
vector<bool> removed(M, false);
// Insertar todos los positivos en el pq
for (int i = 0; i < M; i++) {
if (B[i] > 0) {
pq.push({B[i], startIdx[i], i - 1, i + 1});
}
}
// Eliminar K veces el menor positivo
for (int iter = 0; iter < K; iter++) {
if (pq.empty()) break;
Node cur = pq.top();
pq.pop();
// Verificar si este nodo ya fue invalidado
if (removed[cur.idx]) continue;
// Marcar como procesado
removed[cur.idx] = true;
// Combinar con vecinos
int L = cur.l;
int R = cur.r;
// Encontrar vecinos válidos (no eliminados)
while (L >= 0 && removed[L]) L--;
while (R < M && removed[R]) R++;
if (L >= 0 && R < M) {
// Ambos vecinos existen: combinar los tres
// El menor valor absorbe a los otros dos
long long vals[3] = {B[cur.idx], B[L], B[R]};
// Encontrar el índice del menor
int minIdx = 0;
if (vals[1] < vals[minIdx]) minIdx = 1;
if (vals[2] < vals[minIdx]) minIdx = 2;
if (minIdx == 0) {
// El actual absorbe a ambos
B[cur.idx] = B[L] + B[cur.idx] + B[R];
removed[L] = removed[R] = true;
// Actualizar vecinos del nuevo nodo
int newL = L - 1;
while (newL >= 0 && removed[newL]) newL--;
int newR = R + 1;
while (newR < M && removed[newR]) newR++;
// Insertar de nuevo si es positivo
if (B[cur.idx] > 0) {
pq.push({B[cur.idx], startIdx[cur.idx], newL, newR});
}
} else if (minIdx == 1) {
// Izquierdo absorbe
B[L] = B[L] + B[cur.idx] + B[R];
removed[cur.idx] = removed[R] = true;
int newL = L - 1;
while (newL >= 0 && removed[newL]) newL--;
int newR = R + 1;
while (newR < M && removed[newR]) newR++;
if (B[L] > 0) {
pq.push({B[L], startIdx[L], newL, newR});
}
} else {
// Derecho absorbe
B[R] = B[L] + B[cur.idx] + B[R];
removed[cur.idx] = removed[L] = true;
int newL = L - 1;
while (newL >= 0 && removed[newL]) newL--;
int newR = R + 1;
while (newR < M && removed[newR]) newR++;
if (B[R] > 0) {
pq.push({B[R], startIdx[R], newL, newR});
}
}
} else if (L >= 0) {
// Solo vecino izquierdo
B[L] += B[cur.idx];
removed[cur.idx] = true;
int newL = L - 1;
while (newL >= 0 && removed[newL]) newL--;
if (B[L] > 0) {
pq.push({B[L], startIdx[L], newL, L + 1});
}
} else if (R < M) {
// Solo vecino derecho
B[R] += B[cur.idx];
removed[cur.idx] = true;
int newR = R + 1;
while (newR < M && removed[newR]) newR++;
if (B[R] > 0) {
pq.push({B[R], startIdx[R], R - 1, newR});
}
}
// Si no hay vecinos, simplemente se elimina (queda en 0)
}
// ===== FASE 4: Calcular respuesta =====
long long ans = 0;
for (int i = 0; i < M; i++) {
if (!removed[i] && B[i] > 0) {
ans += B[i];
}
}
cout << ans << "\n";
return 0;
}
