#include <fstream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>

#define maxn 10010
#define maxk 1010

using namespace std;

ifstream fin("ferma.in");
ofstream fout("ferma.out");

int a[maxn];
int v[maxn];
int dp[2][maxn],ok;
int s,n,k,current,ans,nr,currents,t,maxv;

int main()
{
    fin>>n>>k;

    for (int i=1; i<=n; ++i)
    {
        fin>>a[i];

        if (a[i] > 0)
        {
            ++nr;
        }
    }

    if (nr <= k)
    {
        nth_element (a+1,a+n-k+1,a+n+1);

        int p = a[n-k+1];

        for (int i=1; i<=n; ++i)
        {
            if (a[i] > p)
            {
                s += a[i];
                --k;
            }
        }

        s += p*k;

        fout<<s;
        return 0;
    }

    for (int i=1; i<=n; ++i)
    {

        if ((a[i] >= 0) == (currents >= 0) || currents == 0)
        {
            currents += a[i];
        }
        else
        {
            ++t;

            if (currents >= 0)
            {
                v[t] = -currents;
                s += currents;
            }
            else v[t] = currents;

            currents = a[i];
        }
    }

    if ( (currents >= 0) == (a[1] >= 0) )
    {
        if (currents >= 0)
        {
            v[1] -= currents;
            s += currents;
        }
        else v[1] += currents;
    }
    else
    {
        ++t;
        if (currents >= 0)
            {
                v[t] = -currents;
                s += currents;
            }
            else v[t] = currents;
    }

    k = t/2-k;

    if (k <= 0)
    {
        fout<<s;
        return 0;
    }

    for (int i=1,ii=1; i<=k; ++i, ok = 1-ok, ii+=2)
    {
        if (ii==1) dp[ok][1] = v[1];
        else dp[ok][ii] = dp[1-ok][ii-2]+v[ii];

        for (int j=ii+1; j<t; ++j)
        {
            dp[ok][j] = max (dp[ok][j-1],dp[1-ok][j-2]+v[j]);
        }
    }

    maxv = dp[1-ok][t-1];
    ok = 0;
    memset (dp,0,sizeof(dp));

    for (int i=1,ii=2; i<=k; ++i, ok = 1-ok, ii+=2)
    {
        dp[ok][ii] = dp[1-ok][ii-2] + v[ii];

        for (int j=ii+1; j<=t; ++j)
        {
            dp[ok][j] = max (dp[ok][j-1],dp[1-ok][j-2]+v[j]);
        }
    }

    maxv = max (maxv,dp[1-ok][t]);

    fout<<s+maxv;
}