#include <stdio.h>
#include <memory.h>

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

int first;
int p[NMAX];
int a[2][NMAX];//, aux[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;

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

		for(j = 2; j <= n; ++j)
		{
			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];
		}
	}
    for(j = 1; j <= n; ++j)
          max = MAX(max, a[1-stare][j] + s[n] - s[j] + p[0]);

    return max;
}

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

	read();

	//printf("%d\n", dinamic());

    for(int i = 1; i <= n; ++i)
          s[i] = s[i-1] + p[i];

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

	return 0;
}