#include <stdio.h>

#define NMAX 10005
#define KMAX 1005
#define INFI -(0x3f3f3f3f)

int p[NMAX];
int a[2][NMAX];
int d[NMAX], st, dr;
int s[NMAX];
int n, k;

void read()
{
	int i;
	scanf("%d%d", &n, &k);
	for(i = 1; i <= n; ++i)
		scanf("%d", p+i), s[i] = s[i-1] + p[i];
}

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

int dinamic()
{
	int i, j;
	int stare = 1;
	int max = INFI;
    int crt = INFI;

    for(j = 1; j <= n; ++j)
    {
         crt = MAX(crt+p[j], p[j]);
         max = MAX(max, crt);
         a[0][j] = max;
    }

	for(i = 2; i <= k; ++i, stare = 1-stare)
	{
		a[stare][1] = p[1];
		d[1] = 0;
		st = dr = 1;

		for(j = 2; j <= n; ++j)
		{
		//	if(i!=1)
             a[stare][j] = MAX(a[stare][j-1], d[st] + s[j]);


     		while(st <= dr && d[dr] <= a[1-stare][j] - s[j])
				--dr;
			d[++dr] = a[1-stare][j] - s[j];
		}
	}
    max = a[1-stare][n];

    for(j = 1; j < n; ++j)
	    max = MAX(max, a[1-stare][j] + s[n] - s[j]);
    
    return max;
}

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

	read();

	int x=  dinamic();
 if(x <= 0)
  printf("0\n");
  else printf("%d", x);


	return 0;
}