#include<stdio.h>
#define MIN -1000000100
int n,nr,x[10001];
long a[1010][2],b[1010][2];
void READ(){
int i;
FILE *f;

   f=fopen("ferma.in","r");
   fscanf(f,"%d %d",&n,&nr);
   for(i=1;i<=n;i++)
	fscanf(f,"%d",&x[i]);
}

long max(long x,long y)
{
  if (x>y) return x;
  return y;
}

long SOLVE1(){
int i,k;

   for(i=0;i<=nr;i++) b[i][0]=b[i][1]=MIN;

   b[0][0]=0; b[1][1]=x[1];

   for(i=2;i<=n;i++){
	for(k=0;k<=nr;k++){
		a[k][0]=max(b[k][0],b[k][1]);

		if(k>=1){
			a[k][1]=max(b[k-1][0],b[k-1][1]);
			if(a[k][1]!=MIN) a[k][1]+=x[i];

			if(b[k][1]!=MIN && b[k][1]+x[i]>a[k][1]) a[k][1]=b[k][1]+x[i];
		}
	}
   for(k=0;k<=nr;k++){
      b[k][0]=a[k][0];
      b[k][1]=a[k][1];
      a[k][0]=a[k][1]=MIN;
   }


   }
return max(b[nr][0],b[nr][1]);

}

long SOLVE2(){
int i,k;

   for(i=0;i<=nr;i++) b[i][0]=b[i][1]=MIN;
   b[1][1]=x[1];

   for(i=2;i<=n;i++){
	for(k=0;k<=nr+1;k++){
		a[k][0]=max(b[k][0],b[k][1]);

		if(k>=1){
			a[k][1]=max(b[k-1][0],b[k-1][1]);
			if(a[k][1]!=MIN) a[k][1]+=x[i];

			if(b[k][1]!=MIN && b[k][1]+x[i]>a[k][1]) a[k][1]=b[k][1]+x[i];
		}

	}
   for(k=0;k<=nr+1;k++){
      b[k][0]=a[k][0];
      b[k][1]=a[k][1];
      a[k][0]=a[k][1]=MIN;
   }
   }
return b[nr+1][1];
}


int main()
{  long A,B;
   READ();
   A=SOLVE1();
   B=SOLVE2();

   if(A<B) A=B;
   FILE *g;
   g=fopen("ferma.out","w");
   fprintf(g,"%ld\n",A);
   fclose(g);
return 0;
}