#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 10005
#define MAX 1005

int a[2][MAX],b[2][MAX];
int n,k,nrt;
int v[DIM];

void read ()
{
    int i;

    scanf ("%d%d",&n,&k);
    for (i=1; i<=n; ++i)
        scanf ("%d",&v[i]);
}

void solve ()
{
    int i,j,i1,i2;

    memset (a[0],-INF,sizeof (a[0]));
    memset (b[0],-INF,sizeof (b[0]));
    for (i1=0, i=i2=1; i<=n; ++i, i1^=i2^=i1^=i2)
    {
        memset (a[i2],0,sizeof (a[i2]));
        memset (b[i2],0,sizeof (b[i2]));
        for (j=i+1; j<=k; ++j)
            a[i2][j]=b[i2][j]=-INF;
        for (j=1; j<=min (i,k); ++j)
        {
            a[i2][j]=max (a[i1][j-1],max (a[i1][j],b[i1][j-1]))+v[i];
            b[i2][j]=max (a[i1][j],b[i1][j]);
        }
    }
    nrt=max (a[i1][k],b[i1][k]);

	++k;
    memset (a[0],-INF,sizeof (a[0]));
    memset (b[0],-INF,sizeof (b[0]));
	a[0][1]=b[0][1]=v[1];
	for (i1=0, i2=1, i=2; i<=n; ++i, i1^=i2^=i1^=i2)
    {
		memset (a[i2],0,sizeof (a[i2]));
        memset (b[i2],0,sizeof (b[i2]));
		for (j=i+1; j<=k; ++j)
            a[i2][j]=b[i2][j]=-INF;
        for (j=1; j<=min (i,k); ++j)
        {
            if (j>1)
                a[i2][j]=max (a[i1][j-1],max (a[i1][j],b[i1][j-1]))+v[i];
            else
                a[i2][j]=a[i1][j]+v[i];
			b[i2][j]=max (a[i1][j],b[i1][j]);
		}
	}
	nrt=max (nrt,a[i1][k]);
	printf ("%d",nrt);
}

int main ()
{
    freopen ("ferma.in","r",stdin);
    freopen ("ferma.out","w",stdout);

    read ();
    solve ();

    return 0;
}