#include<stdio.h>
#define Nmax 10004
#define Kmax 1003

int P[Nmax],A[Kmax][Nmax],S[Nmax];

int main()
{
FILE *fin=fopen("ferma.in","r"),
     *fout=fopen("ferma.out","w");
     
int N,i,K,max,min,j,sol1,sol2;

fscanf(fin,"%d%d",&N,&K);
for(i=1;i<=N;i++)
  {
  fscanf(fin,"%d",&P[i]);
  S[i]=S[i-1]+P[i];
  }
  
//prima dinamica
min=0;  
for(i=1;i<=N;i++)
  {
  A[1][i]= S[i]-min;
  if(S[i] < min)
    min=S[i];
  
  if(i-1)
   if(A[1][i-1]>A[1][i])
      A[1][i]=A[1][i-1];
  }
  
for(i=2;i<=K;i++)
  {
  max=0;
  A[i][i]=A[i-1][i-1]+S[i]-S[i-1];
  
  if(A[i-1][i-1]-S[i-1] > max)
     max=A[i-1][i-1]-S[i-1];
  
  if(A[i-1][i]-S[i] > max)
     max=A[i-1][i]-S[i];
  
  for(j=i+1;j<=N;j++)
    {
    A[i][j]=A[i][j-1];
    
    if(max+S[j] > A[i][j])
       A[i][j]= max + S[j];
      
    if(A[i-1][j]-S[j] > max)
       max=A[i-1][j]- S[j];
    }                   
  }
sol1=A[K][N];
  
//a doua dinamica
for(i=1;i<=N;i++) 
   {                  
   A[1][i]=S[i];   
   
   if(i-1)
     if(A[1][i] < A[1][i-1])
        A[1][i]=A[1][i-1];
   }

for(i=2;i<=K;i++)
  {
  max=0;
  A[i][i]=A[i-1][i-1]+S[i]-S[i-1];
  
  if(A[i-1][i-1]-S[i-1] > max)
     max=A[i-1][i-1]-S[i-1];
  
  if(A[i-1][i]-S[i] > max)
     max=A[i-1][i]-S[i];
  
  for(j=i+1;j<=N;j++)
    {
    A[i][j]=A[i][j-1];
    
    if(max+S[j] > A[i][j])
       A[i][j]= max + S[j];
      
    if(A[i-1][j]-S[j] > max)
       max=A[i-1][j]- S[j];
    }                   
  }
  
sol2=0;
for(i=K;i<=N;i++)
  if(sol2 < A[K][i]+S[N]-S[i])
     sol2 = A[K][i]+S[N]-S[i];

if(sol1 < sol2)
   sol1 = sol2;
if(sol1<0) sol1=0;
fprintf(fout,"%d\n",sol1);

fclose(fin);
fclose(fout);
return 0;         
}