#include <fstream>
#include <cstring>
using namespace std;

const int N = 1 + 1e4, K = 1 + 1e3, inf = 0x1f1f1f1f;

int strict[K], lax[K], val[N], n, k;

void compress(int v[], int& size){
    int n = 1;
    for (int i = 2 ; i <= size ; i++)
        if ( (long long)v[i] * v[n] >= 0 )
            v[n] += v[i];
        else
            v[++n] = v[i];
    size = n;
}

int compute(int val[], int n, int k){
    memset(strict, 0, sizeof(strict));
    memset(lax, 0, sizeof(lax));
    for (int i = 1 ; i <= n ; i++)
        for (int j = k ; j ; j--){
            strict[j] = max(strict[j], lax[j - 1]) + val[i];
            lax[j] = max(strict[j], lax[j]);
        }
    int ans = 0;
    for (int i = 1 ; i <= k ; i++)
        ans = max(ans, lax[i]);
    return ans;
}

int main(){
    int n, k;
    ifstream in("ferma.in");

    in >> n >> k;
    for (int i = 1 ; i <= n ; i++)
        in >> val[i];
    in.close();

    compress(val, n);
    val[0] = val[n + 1] = inf;

    ofstream out("ferma.out");
    out << max( compute(val, n, k), compute(val - 1, n + 2, k + 1) - 2 * inf ) << '\n';
    out.close();

    return 0;
}