#include<stdio.h>
#define NMAX 10024
#define inf 1<<30

int V[NMAX],S[NMAX];
int SOL[2][NMAX];

void swap(int &a,int &b)
{
     a^=b; b^=a; a^=b;
}

inline int max(const int a,const int b)
{
       return a>b?a:b;
}

int sf;

int main()
{
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);
    
    int N,K;
    scanf("%d%d",&N,&K);
    
    int i,j;
    for(i=1; i<=N; ++i)
    {
              scanf("%d",&V[i]);
              S[i]=S[i-1]+V[i];
    }
    
    int curr=0,prev=1;
    int inc,a1;
    int MAX;//bogdan2412 rules
    for(i=1; i<=K; ++i)
    {
             swap(curr,prev);
             
             MAX=SOL[prev][i-1]-S[i-1];
             
             SOL[curr][i]=max(SOL[prev][i-1]+V[i],SOL[prev][i-1]);
             SOL[curr][i-1]=0;
             
             for(j=i+1; j<=N; ++j)
             {
                      MAX=max( SOL[prev][j-1]-S[j-1], MAX );  
                      SOL[curr][j]=max( MAX+S[j], SOL[curr][j-1] );
             }
    }
    
    int ANS=max(SOL[curr][N],0);
    
    ++K;
    for(i=1; i<=N; ++i)
             SOL[curr][i]=S[i];
    
    for(i=2; i<=K; ++i)
    {
             swap(curr,prev);
             
             MAX=SOL[prev][i-1]-S[i-1];
             
             SOL[curr][i]=max(SOL[prev][i-1]+V[i],SOL[prev][i-1]);
             SOL[curr][i-1]=0;
             
             for(j=i+1; j<=N; ++j)
             {
                      MAX=max( SOL[prev][j-1]-S[j-1], MAX );  
                      SOL[curr][j]=max( MAX+S[j], SOL[curr][j-1] );
             }
    }
    
    int ANS2=0;
    for(i=1; i<=N; ++i)
    ANS2=max(ANS2,SOL[curr][i]+S[N]-S[i]);
    
    ANS=max(ANS,ANS2);
    
    printf("%d\n",ANS);  
    
    return 0;
}