#include <cstdio>
#include <cstring>

#define Nmax 10001
#define Kmax 1001

int N, K, i, j, aux, p, best;
int A[Nmax], S[Nmax], B[2][Kmax], C[2][Kmax];

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

void dinamica(int st)
{  
     int ind = 1;
     
     memset(C, 0, sizeof(C));
     memset(B, 0, sizeof(B));
     
     for (i=0; i<=K; ++i)
         C[0][i] = B[0][i] = -2000000000;
     
     C[0][st-1] = B[0][st-1] = A[st-1];
     
     for (i=st; i<=N; ++i, ind^=1)
     {
         if (st==2) B[ind][1] = B[ind^1][1] + A[i], C[ind][1] = max( B[ind][1], C[ind^1][1] );         
         for (j=st; j<=K && j<=i; ++j)
         {
             B[ind][j] = max( C[ind^1][j-1] + A[i], B[ind^1][j] + A[i] );
             C[ind][j] = max( B[ind][j], C[ind^1][j]);
         }
      if (st==2) best = max(best, C[ind][K] + S[N] - S[i]);
     }
             
     if (st==1) best = max(best, C[ind^1][K]);
             
}

int main()
{
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);
    
    scanf("%d %d", &N, &K);
    for (i=1; i<=N; ++i)
        scanf("%d", &A[i]), S[i] = S[i-1] + A[i];
        
    best = 0;
    
    dinamica(1);    
    dinamica(2);
    
    printf("%d\n", best);    
    
    return 0;
}