#include<iostream>
#include<fstream>

#define inf 1000000

using namespace std;

int a[4][10005],b[4][10005],v[10005],n,k,sol;

void solve()
{
	int c1,c2,i,q;
	
	c1=0;c2=1;
	a[c1][1]=v[1]; b[c1][1]=-inf;
	
	for (i=2;i<=n;i++)
	{
		a[c1][i]=a[c1][i-1]+v[i];
		if (a[c1][i]<v[i])
			a[c1][i]=v[i];
		
		b[c1][i]=b[c1][i-1];
		if (b[c1][i]<a[c1][i-1])
			b[c1][i]=a[c1][i-1];	
	}
	
	c1=(c1^c2)^(c2=c1);
	
	for (q=2;q<=k;q++)
	{
		a[c1][q]=a[c2][q-1]+v[q];
		b[c1][q]=-inf;
		
		for (i=q+1;i<=n;i++)
		{
			a[c1][i]=a[c1][i-1]+v[i];
			if (a[c1][i]<b[c2][i-1]+v[i])
				a[c1][i]=b[c2][i-1]+v[i];
			if (a[c1][i]<a[c2][i-1]+v[i])
				a[c1][i]=a[c2][i-1]+v[i];
			
			b[c1][i]=b[c1][i-1];
			if (b[c1][i]<a[c1][i-1])
				b[c1][i]=a[c1][i-1];
		}
		
		c1=(c1^c2)^(c2=c1);
	}
	
	sol=max(sol,max(a[c2][n],b[c2][n]));
	

	c1=0;c2=1;
	a[c1][0]=0;

	for (i=1;i<=n;i++)
	{
		a[c1][i]=a[c1][i-1]+v[i];
		b[c1][i]=a[c1][i-1];
	}
	b[c1][1]=-inf;
	
	c1=(c1^c2)^(c2=c1);
	
	for (q=2;q<=k+1;q++)
	{
		a[c1][q]=a[c2][q-1]+v[q];
		b[c1][q]=-inf;
		
		for (i=q+1;i<=n;i++)
		{
			a[c1][i]=a[c1][i-1]+v[i];
			if (a[c1][i]<b[c2][i-1]+v[i])
				a[c1][i]=b[c2][i-1]+v[i];
			if (a[c1][i]<a[c2][i-1]+v[i])
				a[c1][i]=a[c2][i-1]+v[i];
			
			b[c1][i]=b[c1][i-1];
			if (b[c1][i]<a[c1][i-1])
				b[c1][i]=a[c1][i-1];
		}
		
		c1=(c1^c2)^(c2=c1);
	}
	
	sol=max(sol,a[c2][n]);
}

void citire()
{
	int i;
	ifstream f("ferma.in");
	f>>n>>k;
	for (int i=1;i<=n;i++)
		f>>v[i];
	f.close();
}

void afisare()
{
	ofstream g("ferma.out");
	g<<sol;
	g.close();
}

int main()
{
	citire();
	solve();
	afisare();
	return 0;
}