// KZ's
#include <fstream>
using namespace std;
int mp[10003]={0};
int ck(int a,int b) {
	int s,mxs;
	s=mxs=mp[a];
	for (int i=a+1;i<b;i++) {
		s+=mp[i];
		if (s>mxs)
			mxs=s;
		else
			if (s<0)
				s=0;
	}
	return mxs;
}
int f[10003][1003]={0};
int main() {
	ifstream fin ("KPengshuangcang.in");
	ofstream fout ("KPengshuangcang.out");
	int N,K;
	
	fin>>N>>K;
	for (int i=0;i<N;i++)
		fin>>mp[i];
	int s=0,mxs=0;
	f[0][1]=mp[0];
	s=mp[0];
	mxs=mp[0];
	for (int i=1;i<N;i++) {
		s+=mp[i];
		if (s>mxs)
			mxs=s;
		else
			if (s<0)
				s=0;
		f[i][1]=mxs;
	}
	for (int k=2;k<=K;k++)
		for (int i=2*k-4;i<N;i++)
			for (int j=i+1;j<=N;j++)
				f[i][k]=max(f[i][k],f[i][k-1]+ck(i+2,j));
	fout<<f[N-1][K]<<endl;
	return 0;
}
// UBWH