#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 10010
#define MAX_K 1024

int n, k, t, l, dr, sol;
int A[MAX_N], sum[MAX_N];
int d[MAX_N], c[MAX_N][2];

void cit() {
    freopen("ferma.in", "r", stdin);
	freopen("ferma.out", "w", stdout);

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

void push(int poz) {
	d[++dr] = poz;

	while (c[d[dr]][1 - l] > c[d[dr - 1]][1 - l] + sum[poz] - sum[d[dr - 1]] && dr > 1) {
		d[dr - 1] = d[dr];
		dr--;
	}
}
                                                      
void solve() {
	for (t = 0; t < 2; t++) {
    	//t = 0 nu iau primul element, t = 1 iau primul element
    	
		l = 0;
		for (int j = 1; j <= k; j++) {
			l = 1 - l; dr = 0;
		
			for (int i = j; i <= n; i++) {
				if (t && j == k && i == n) break;
				if (t && j == 1) d[1] = 0;
				
				c[i][l] = max(c[d[1]][1 - l] + sum[i] - sum[d[1]], c[i - 1][l]);
				push(i);
			}
			
			if (t && j == k)
				for (int i = k; i < n; i++)      	
					c[n][l] = max(c[n][l], c[i][l] + sum[n] - sum[i]);

			if (j == k)
				sol = max(sol, c[n][l]);
			
			for (int i = 1; i <= n; i++)
				c[i][1 - l] = d[i] = 0;
		}
		for (int i = 1; i <= n; i++)
			c[i][l] = 0;
	}

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

int main() {

	cit();
	solve();
	
	return 0;
}