#include <cstdio>
#include <cstring>
#define maxn 10100
#define inf 2000000000

using namespace std;

int n, k, i, j;
int v[maxn], sum[maxn];
int d[2][maxn], mx[2][maxn];
int dq[maxn], sus, jos;
int sol;

inline int func(int l, int r) {
	return mx[0][l - 1] + sum[r] - sum[l - 1];
}

inline int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

inline void dinamica() {

	for (i = 1; i <= k; i++) {
		sus = 0; jos = 1;
		mx[1][0] = -inf;

		for (j = 1; j <= n; j++) {
			//bag in deque pozitia j

			while (func(j, j) > func(dq[sus], j) && sus >= jos) 
				sus--;

			sus++;
			dq[sus] = j;

			d[1][j] = func(dq[jos], j);
//			fprintf(stderr, "%d ", d[1][j]);
			mx[1][j] = max(mx[1][j - 1], d[1][j]);
		}

//		fprintf(stderr, "\n");
		memcpy(d[0], d[1], sizeof(d[0]));
		memcpy(mx[0], mx[1], sizeof(mx[0]));
	}
}

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

	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
		sum[i] = sum[i - 1] + v[i];
	}


	//d[i][j] -> grupa cu numarul i sa mi se termine pe pozitia j
	

	dinamica();

	sol = mx[0][n];

	for (i = 1; i <= n; i++) {
		d[0][i] = sum[i];
		mx[0][i] = max(mx[0][i - 1], d[0][i]);
	}

	dinamica();

	for (i = 1; i <= n; i++)
		sol = max(sol, d[0][i] + sum[n] - sum[i]);

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

	return 0;
}