#include<stdio.h>
#define nmax 10002
long start,end,sf,inc,n;
long init(long s[nmax]);long secv_max(long s[nmax]);long secv_min(long s[nmax]);
long secv[nmax][500],sec[nmax][500];

int main()
{long k,i,ss[nmax],start,end,start1,end1,s,s1;
 long j,max,total=0,d,min;
 freopen("ferma.in","r",stdin);
 scanf("%ld%ld",&n,&k);
 for(i=1;i<=n;i++)
  scanf("%ld",&ss[i]);
 total=init(ss);
 for(i=1;i<k;i++)
  {
   for(j=1,max=0;j<=secv[0][0];j++)
	if(secv_max(secv[j])>max)
	 {max=secv_max(secv[j]);
	  start=inc;
	  end=sf;
	  s=j;
	  }


	for(j=1,min=0;j<=sec[0][0];j++)
	 if(secv_min(sec[j])<min)
	  {min=secv_min(sec[j]);
	   start1=inc;
	   end1=sf;
	   s1=j;
	   }


	if(-min>=max&&min)
	  {for(j=start1,d=++secv[0][0];j<=end1;j++)
		secv[d][j-start1+1]=sec[s1][j];
	   secv[d][0]=end1-start1+1;
	   for(j=end1+1,d=++sec[0][0];j<=sec[s1][0];j++)
		sec[d][j-end1]=sec[s1][j];
	   sec[d][0]=sec[s1][0]-end1;
	   sec[s1][0]=start-1;
	   total-=min;
	  }
	if(max>-min&&max)
	  {total+=max;
	   for(j=start,d=++sec[0][0];j<=end;j++)
			sec[d][j-start+1]=secv[s][j];

	   if(start!=1&&end!=secv[s][0])
		 {for(j=end+1,d=++secv[0][0];j<=secv[s][0];j++)
			secv[d][j-end]=secv[s][j];
		  secv[s][0]=start-1;
		  }
	   else
		 {if(start!=1)
			 secv[s][0]=start-1;
		  if(end!=secv[s][0])
			{
			 for(j=end+1;j<=secv[s][0];j++)
			   secv[s][j-end]=secv[s][j];
			 secv[s][0]=secv[s][0]-end;

			 }
		   }
		}

  }
 freopen("ferma.out","w",stdout);
 printf("%ld",total);
 fclose(stdout);
 return 0;
 }

long init(long s[nmax])
{long i,j,start,inc,sf,end,coada,max;
 for(i=n+1;i<=2*n;i++)
   s[i]=s[i-n];
 coada=0;
 inc=0;//=sf=0;
 max=0;
 s[0]=0;
 for(i=1;i<=2*n;i++)
   {coada+=s[i-1];
	if(i-inc+1>n)
	  coada-=s[inc++];
	if(coada<0)
	  {coada=0;
	   inc=i;
	   }

	if(coada+s[i]>max)
	 {max=coada+s[i];
	  start=inc;
	  end=i;
	  }
	}
 if(max>0)
 {  for(i=start-1;i<end;i++)
	 sec[1][++sec[1][0]]=s[i%n+1];
 sec[0][0]=1;
 if(end>n)
 {i=end-n+1;
 for(;i<start;i++)
   {secv[1][++secv[1][0]]=s[i];
	secv[0][0]=1;
	}
 }
 else
   {for(i=end+1;i<=n;i++)
	 {secv[1][++secv[1][0]]=s[i];
	  secv[0][0]=1;
	  }
	for(i=1;i<start;i++)
	 {secv[1][++secv[1][0]]=s[i];
	  secv[0][0]=1;
	  }
	}


 }
 return max;
 }

long secv_max(long s[nmax])
{long coada=0,in,max=0,i,j;
 in=sf=0;
 if(s[1]>0) {coada=s[1];max=s[1];}
 for(i=2;i<=s[0];i++)
   {coada+=s[i-1];
	if(coada<0)
	  {coada=0;
	   in=i;
	   }
	if(coada+s[i]>max)
	  {max=coada+s[i];
	   inc=in;
	   sf=i;
	   }
	}
 return max;
 }

long secv_min(long s[nmax])
{long i,s1[nmax];
 for(i=1;i<=s[0];i++)
  s1[i]=s[i]*(-1);
 s1[0]=s[0];
 return -(secv_max(s1));
 }