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

inline int max(int a, int b){
	if (a>b)
		return a;
	return b;
}
int a[dimk][dimn], v[dimn], sp[dimn];
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]);
		sp[i] = sp[i - 1] + v[i];
	}
		
	fclose(f);
	
	
	for (int i = 1; i <= k; ++i)
	{
		int sum = 0;
		for (int j = 1; j <= n; ++j)
		{
			a[i][j] = max(a[i][j-1],sum+sp[j]);
			sum = max(sum, a[i - 1][j] - sp[j]);
		}
	}
	int sol = a[k][n];

	memset(a, 0, sizeof(a));
	a[1][1] = v[1];
	for (int i = 2; i <= n; ++i)
	{
		a[1][i] = max(a[1][i - 1], sp[i]);
	}
	
	for (int i = 2; i <= k; ++i)
	{
		a[i][1] = v[1];
		int sum = 0;
		for (int j = 2; j <= n; ++j)
		{
			a[i][j] = max(a[i][j - 1], sum + sp[j]);
			sum = max(sum, a[i - 1][j] - sp[j]);
		}
	}

	int sum = 0;
	for (int i = 1; i <= n; ++i)
		sum = max(sum, a[k][i - 1] - sp[i]);

	sol = max(sol, max(a[k][n], sum + sp[n]));

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

	return 0;
}