#include <stdio.h>

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

int p[NMAX];
int a[KMAX][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;

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

	for(i = 1; i <= k; ++i, stare = 1-stare)
	{
		a[stare][1] = p[1];
		max = 0;
	
		for(j = 2; j <= n; ++j)
		{
			if(i != 1)
				a[stare][j] = MAX(a[stare][j-1], max + s[j]);
			else
				a[stare][j] = MAX(a[stare][j-1]+p[j], p[j]);

     			if(i != 1)
				max = MAX(max, a[1-stare][j] - s[j]);
		}
       for(j = 1; j <= n; ++j)
       printf("%d ", a[stare][j]);
       printf("\n");
	}
   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();

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

	return 0;
}