#include <stdio.h>
#include <string>

#define maxn 10010
#define maxx 1010

int n,m,sol;
int a[maxn],s[maxn],smax[maxn];
int c[maxx],best[maxx];

int main()
{
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);
    
    int i,j;
    scanf("%d %d ",&n,&m);
    for (i=1;i<=n;i++) scanf("%d ",&a[i]);
    
    for (i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    
    for (i=n;i>0;i--) 
      if (s[n]-s[i]>smax[i+1]) smax[i]=s[n]-s[i];
      else smax[i]=smax[i+1];
    
    memset(best,-1,sizeof(best));
    best[0]=0;
    
    for (i=1;i<=n;i++)
    {
      for (j=1;j<=m;j++) 
        if ((best[j-1]!=-1) && (best[j-1]+s[i]>c[j])) c[j]=best[j-1]+s[i];
      
      for (j=0;j<m;j++) 
        if (c[j]-s[i]>best[j]) best[j]=c[j]-s[i];
    }
    
    sol=c[m];
    
    memset(c,0,sizeof(c));
    memset(best,-1,sizeof(best));
    
    for (i=1;i<=n;i++)
    {
        if (s[i]>c[1]) c[1]=s[i];
        
        for (j=2;j<=m;j++) 
          if ((best[j-1]!=-1) && (best[j-1]+s[i]>c[j])) c[j]=best[j-1]+s[i];
          
        for (j=1;j<m;j++)
          if (c[j]-s[i]>best[j]) best[j]=c[j]-s[i];
          
        if (c[m]+smax[i+1]>sol) sol=c[m]+smax[i+1];
    }
       
    printf("%d\n",sol);
    
    return 0;
}