#include <stdio.h>
#include <string.h>

#define KMAX 1111
#define NMAX 11111

#define INF 1000000666

#define maxim(a, b) ((a) > (b) ? (a) : (b))

int mx[2][2][KMAX], max1, max2;
int oua[NMAX];
int i, j, k, N, K, c, a;

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

	scanf("%d %d", &N, &K);
	for (i = 1; i <= N; i++)
		scanf("%d", &oua[i]);

	/* dinamica 1 : 1 si N nu sunt in aceeasi secventa */
	c = 0;

	for (i = 0; i <= K; i++)
		mx[c][0][i] = mx[c][1][i] = -INF;

	mx[c][0][0] = 0;

	for (i = 1; i <= N; i++)
	{
		a = c;
		c = 1 - c;

		mx[c][0][0] = mx[a][0][0];
		mx[c][1][0] = -INF;

		for (j = 1; j <= K; j++)
		{
			mx[c][0][j] = maxim(mx[a][0][j], mx[a][1][j]);
			mx[c][1][j] = oua[i] + maxim(mx[a][1][j], (maxim(mx[a][0][j - 1], mx[a][1][j - 1])));
		}
	}

	max1 = maxim(mx[c][0][K], mx[c][1][K]);

	/* dinamica 2 : 1 si N sunt in aceeasi secventa */
	c = 0;

	for (i = 0; i <= K + 1; i++)
		mx[c][0][i] = mx[c][1][i] = -INF;

	mx[c][1][1] = oua[1];

	for (i = 2; i <= N; i++)
	{
		a = c;
		c = 1 - c;

		mx[c][0][0] = mx[a][0][0];
		mx[c][1][0] = -INF;

		for (j = 1; j <= K + 1; j++)
		{
			mx[c][0][j] = maxim(mx[a][0][j], mx[a][1][j]);
			mx[c][1][j] = oua[i] + maxim(mx[a][1][j], (maxim(mx[a][0][j - 1], mx[a][1][j - 1])));
		}
	}

	max2 = mx[c][1][K + 1];

	freopen("ferma.ok", "w", stdout);

	max1 = maxim(max1, max2);
	if (max1 < 0)
		max1 = 0;

	printf("%d\n", max1);

	return 0;
}