#include <fstream>
#define MAXN 10005
#define INF 2000000000
using namespace std;
ifstream f("ferma.in");
ofstream g("ferma.out");

int n, k, v[MAXN], Sp[MAXN], pd[2][MAXN], maxpd[2][MAXN], act, prev = 1, val, mxi, sol;

inline int MAX(int a, int b){
	return (a > b)?a:b;
}

void compute_pd(int k);

int main(){
	int i;

	f >> n >> k;
	for(i = 1; i <= n; i++){
		f >> v[i];
		Sp[i] = Sp[i - 1] + v[i];
	}

	pd[act][0] = maxpd[act][0] = -INF;
	compute_pd(k);

	sol = maxpd[prev][n];

	pd[prev][0] = maxpd[prev][0] = -INF;
	for(i = 1; i <= n; i++){
		pd[prev][i] = Sp[i];
		maxpd[prev][i] = MAX(pd[prev][i - 1], pd[prev][i]);
	}
	//g << "\n\n\n";
	compute_pd(k - 1);
	for(i = n - 1; i >= 0; i--){
		if(Sp[n] - Sp[i] + maxpd[prev][i] > sol)
			sol = Sp[n] - Sp[i] + maxpd[prev][i];
	}

	g << sol << '\n';

	f.close();
	g.close();
	return 0;
}

void compute_pd(int k){
	int i;
	while(k--){
		mxi = 0;
		for(i = 1; i <= n; i++){
			pd[act][i] = Sp[i] - Sp[mxi] + maxpd[prev][mxi];
			maxpd[act][i] = MAX(maxpd[act][i - 1], pd[act][i]);
			val = maxpd[prev][i] - Sp[i];
			if(val > maxpd[prev][mxi] - Sp[mxi])
				mxi = i;
		}

		/*for(i = 1; i <= n; i++)
			g << pd[act][i] << ' ';
		g << "\n";*/
		swap(act, prev);
	}
}