#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 10015

int n, k;
int sir[Nmax];
int d[2][Nmax][2];
int dr[Nmax];

void citire()
{
	int i;

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

void solve()
{
	int i, j, sol = 0, step = 1;

    memset(d[0], 0, sizeof(d[0]));
	for (j = 1; j <= k; ++j, step = !step)
		for (i = 1; i <= n; ++i)
		{
			d[step][i][0] = max(max(d[!step][i][0], d[step][i - 1][0] + sir[i]), d[!step][i - 1][1] + sir[i]);
			d[step][i][1] = max(d[!step][i][1], d[step][i - 1][1]);

			d[step][i][1] = max(d[step][i][1], d[step][i][0]);
		}

	for (i = 1; i <= n; ++i)
		if (sol < d[!step][i][1])
			sol = d[!step][i][1];

	for (i = n; i >= 1; --i)
		dr[i] = dr[i + 1] + sir[i];

	memset(d, 0, sizeof(d));
	step = 0;
	for (i = 1; i <= n; ++i)
	{
		d[step][i][0] = d[step][i - 1][0] + sir[i];

		d[step][i][1] = max(d[!step][i][1], d[step][i - 1][1]);
		d[step][i][1] = max(d[step][i][1], d[step][i][0]);
	}

	step = 1;
	for (j = 2; j <= k; ++j, step = !step)
		for (i = 1; i <= n; ++i)
		{
 			d[step][i][0] = max(max(d[!step][i][0], d[step][i - 1][0] + sir[i]), d[!step][i - 1][1] + sir[i]);
			d[step][i][1] = max(d[!step][i][1], d[step][i - 1][1]);

			d[step][i][1] = max(d[step][i][1], d[step][i][0]);
		}

	for (i = 1; i <= n; ++i)
		if (sol < d[!step][i][1] + dr[i + 1])
			sol = d[!step][i][1] + dr[i + 1];
	
	printf("%d\n", sol);
}

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

	citire();
	solve();

	return 0;
}