#include <bits/stdc++.h>
using namespace std;
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];
// ===== Subtask 1: Todos Ai >= 0 =====
bool todosPositivos = true;
for (int i = 0; i < N; i++) {
if (A[i] < 0) {
todosPositivos = false;
break;
}
}
if (todosPositivos) {
long long suma = 0;
for (int i = 0; i < N; i++) suma += A[i];
cout << suma << "\n";
return 0;
}
// ===== Subtask 2: Maximo un Ai < 0 =====
int negativos = 0;
int posNeg = -1;
for (int i = 0; i < N; i++) {
if (A[i] < 0) {
negativos++;
posNeg = i;
}
}
if (negativos == 0) {
// Ya cubierto por subtask 1
long long suma = 0;
for (int i = 0; i < N; i++) suma += A[i];
cout << suma << "\n";
return 0;
}
if (negativos == 1) {
// Calcular suma izquierda y derecha
long long sumaIzq = 0, sumaDer = 0, sumaTotal = 0;
for (int i = 0; i < N; i++) {
sumaTotal += A[i];
if (i < posNeg) sumaIzq += A[i];
if (i > posNeg) sumaDer += A[i];
}
long long ans = max({sumaIzq, sumaDer, sumaTotal});
cout << ans << "\n";
return 0;
}
// ===== Subtask 3 a 6: DP O(NK) =====
// g[n][k] = max sum with k subarrays, ending at position n (n is chosen)
// f[n][k] = max sum with k subarrays in first n elements
// Inicializar con valores muy negativos
const long long NEG_INF = LLONG_MIN / 4;
// f[i][k] = mejor resultado usando los primeros i elementos (0..i-1) con k subarrays
// g[i][k] = mejor resultado donde el elemento i-1 es seleccionado y pertenece al último subarray
vector<vector<long long>> f(N + 1, vector<long long>(K + 1, NEG_INF));
vector<vector<long long>> g(N + 1, vector<long long>(K + 1, NEG_INF));
// Casos base
f[0][0] = 0; // Sin elementos, sin subarrays = 0
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= K; k++) {
// g[i][k]: el elemento i-1 es seleccionado
// Opción 1: extender el último subarray (g[i-1][k] + A[i-1])
// Opción 2: iniciar nuevo subarray en i-1 (f[i-1][k-1] + A[i-1])
long long opt1 = (g[i-1][k] != NEG_INF) ? g[i-1][k] + A[i-1] : NEG_INF;
long long opt2 = (f[i-1][k-1] != NEG_INF) ? f[i-1][k-1] + A[i-1] : NEG_INF;
g[i][k] = max(opt1, opt2);
// f[i][k]: no tomar i-1 o tomarlo (como parte de g[i][k])
f[i][k] = max(f[i-1][k], g[i][k]);
}
// Para k = 0, solo podemos no tomar nada
f[i][0] = 0;
}
cout << f[N][K] << "\n";
return 0;
}
