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


ifstream f("ferma.in");
ofstream g("ferma.out");
int A[1007][10007],n,k,i,j,suma[10007],x,Prod,Maxim1;
inline int maxim(int a,int b){
	if(a<b)
		return b;
	return a;
}
void dinamica(){
	for(i=1;i<=k;++i){
		
		Prod=0;
		
		for(j=1;j<=n;++j){
			A[i][j]=maxim(A[i][j-1],Prod+suma[j]);
			Prod=max(Prod,A[i-1][j]-suma[j]);
		}
	}
	
	Maxim1=A[k][n];
}
void dinamicaCiclu(){
	
		
	memset(A,0,sizeof(A));
	A[1][1]=suma[1];
	for(i=2;i<=n;++i)
		A[1][i]=maxim(A[1][i-1],suma[i]);
	
	
	for(i=2;i<=k;++i){
		
		A[i][1]=suma[1];
		Prod=0;
		for(j=2;j<=n;++j){
			A[i][j]=maxim(A[i][j-1],Prod+suma[j]);
			Prod=max(Prod,A[i-1][j]-suma[j]);
			
		}
		
	}
	
}
int main (){
	
	f>>n>>k;
	
	//A[i][j]= productivitatea maxima pentru i strangeri din primele j sectoare 
	
	for(i=1;i<=n;++i){
		f>>x;
		suma[i]=suma[i-1]+x;
	}
	
	dinamica();
	dinamicaCiclu();
	Prod=0;
	for(i=1;i<=n;++i)
		Prod=maxim(Prod,A[k][i-1]-suma[i-1]);
	
	g<<maxim(Maxim1,maxim(A[k][n],Prod+suma[n]));
	return 0;
}