#include<stdio.h>
#define inf 1000000001
#define dimk 1003
#define dimn 10003

inline int max(int a, int b){
	if (a>b)
		return a;
	return b;
}
inline int min(int a, int b){
	if (a<b)
		return a;
	return b;
}
int a1[dimk], max1, v[dimn];
int b1[dimk], a2[dimk], b2[dimk];
int main()
{
	FILE*f = fopen("ferma.in", "r");
	int n, k;
	fscanf(f, "%d%d", &n, &k);
	for (int i = 1; i <= n; ++i)
		fscanf(f, "%d", &v[i]);
	fclose(f);
	//a[1][1]=v[1];
	for (int j = 1; j<=k; j++)
		a1[j] = b1[j] = b2[j] = a2[j] = -inf;
	for (int i = 1; i <= n; i++){
		int x = min(i, k);
		for (int j = 1; j <= x; j++){
			a2[j] = max(a1[j] + v[i], b1[j - 1] + v[i]);
			a2[j] = max(a2[j], a1[j - 1] + v[i]);
			b2[j] = max(a1[j], b1[j]);
		}
		for (int j = 1; j <= x; j++){
			a1[j] = a2[j];
			b1[j] = b2[j];
		}
	}
	max1 = max(a1[k], b1[k]);
	k++;

	for (int j = 1; j<=k; j++)
		a1[j] = b1[j] = b2[j] = a2[j] = -inf;

	a1[1] = v[1] ;
	b1[0] = 0;


	for (int i = 2; i <= n; i++){
		int x = min(i, k);
		for (int j = 1; j <= x; j++){
			a2[j] = max(a1[j] + v[i], b1[j - 1] + v[i]);
			a2[j] = max(a2[j], a1[j - 1] + v[i]);
			b2[j] = max(a1[j], b1[j]);
		}
		for (int j = 1; j <= x; j++){
			a1[j] = a2[j];
			b1[j] = b2[j];
		}
	}
	max1 = max(max1, a1[k]);
	max1 = max(max1, 0);

	FILE*g = fopen("ferma.out", "w");
	fprintf(g, "%d", max1);
	fclose(g);

	return 0;
}