#include <cstdio>
#define lm 10010
#define vmx -(1<<30)
#include <algorithm>
using namespace std;

int a[lm], v[lm], b[lm], b2[lm], a2[lm], n, k, vm;

int main()
{
	freopen("ferma.in","r",stdin);
	freopen("ferma.out","w",stdout);
	scanf("%d %d",&n, &k);
	int i, j;
	for (i=1; i<=n; i++) 
	{
		scanf("%d",&v[i]);
		a[i]=vmx;
		b[i]=vmx;
	}
	a[0]=vmx;
	b[0]=vmx;
	for (i=1; i<=k; i++)
	{
		for (j=i; j<=n; j++)
		{
			a[j] = max (a2[j-1]+v[j], b2[j-1]+v[j]);
			a[j] = max (a[j], a[j-1]+v[j]);
			b[j] = max (a[j-1], b[j-1]);
			vm = max(vm, a[j]);
			vm = max(vm, b[j]);
		}
		for (j=i; j<=n; j++) 
		{
			a2[j]=a[j];
			b2[j]=b[j];
		}
	}
	for (i=1; i<=n; i++) 
	{
		b2[i]=0;
		a[i]=vmx;
	}
	b[1]=vmx;
	a[0]=0;
	for (i=1; i<k+2; i++)
	{
		for (j=i; j<=n; j++)
		{
			if (i>1) a[j] = max (a2[j-1]+v[j], b2[j-1]+v[j]);
			a[j] = max (a[j], a[j-1]+v[j]);
			b[j] = max (a[j-1], b[j-1]);
		}
		for (j=i; j<=n; j++) 
		{
			a2[j]=a[j];
			b2[j]=b[j];
		}
	}
	vm = max(vm, a[n]);
	printf("%d",max(0,vm));
}