#include<iostream>
#include<fstream>
using namespace std;

ifstream in("ferma.in");
ofstream out("ferma.out");

const int N = 10010;

int n,k,v[N],s[N],d[1002][N],best,max1;

inline int max(const int &a, const int &b) {
	return a>b ? a : b;
}

int main() {
	int i,j;
	
	in >> n >> k;
	
	for(i = 1; i<=n; ++i) {
		in >> v[i];
		s[i] = s[i-1] + v[i];
	}
	
	for(i = 1; i<=k; ++i) {
		best = 0;
		
		for(j = 1; j<=n; ++j) {
			d[i][j] = max(d[i][j-1], best + s[j]);
			best = max(best, d[i-1][j] - s[j]);
		}
	}
	
	max1 = d[k][n];
	
	for(i = 1; i<=n; ++i)
		d[1][i] = max(d[1][i-1], s[i]);
	
	for(i = 2; i<=k; ++i) {
		best = 0;
		d[i][1] = s[1];
		
		for(j = 1; j<=n; ++j) {
			d[i][j] = max(d[i][j-1], best + s[j]);
			best = max(best, d[i-1][j] - s[j]);
		}
	}
	
	best = 0;
	
	for(i = 1; i<=n; ++i)
		best = max(best, d[k][i] - s[i]);
	
	out << max(max1, best + s[n]) << "\n";
	
	return 0;
}