#include <fstream>
#include <cstring>
#include <algorithm>

#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[maxk][maxn];
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;
            }
        }

        while (k)
        {
            s += p;
            --k;
        }

        fout<<s;
        return 0;
    }

    for (int i=1; i<=n; ++i)
    {
        if ((a[i] >= 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;
        }
        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; i<=k; ++i)
    {
        dp[i][i-1] = 0;
        dp[i][i] = dp[i-1][i-1]+v[i];

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

    maxv = dp[k][t-1];

    memset (dp,0,sizeof(dp));

    for (int i=1; i<=k; ++i)
    {
        dp[i][i] = 0;
        dp[i][i+1] = dp[i-1][i] + v[i+1];

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

    maxv = max (maxv,dp[k][t]);

    fout<<s+maxv;
}