#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 10024
#define INF 2e9
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )

int A[NMAX];
int B1[NMAX], B2[NMAX];
int V[NMAX], S[NMAX], N, K;
int i, j, Sol, ind, val;

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", &V[i]);

     for (i = 1; i <= N; i++) S[i] = V[i] + S[i-1];

     for (i = 1; i <= K; i++)
     {
            val = -INF;

            for (j = 0; j < N; j++)
            {
               if (val <= A[j] - S[j]) val = A[j] - S[j];
               B1[j+1] = val;
            }

            for (j = 1; j <= N; j++)
                A[j] = MAX( A[j-1], B1[j] + S[j]);

            Sol = A[N];
     }

     memset(B1, 0, sizeof(B1));
     memset(A, 0, sizeof(A));

     for (i = 1; i <= N; i++) A[i] = S[i];

     for (i = 1; i <= K; i++)
     {
            val = -INF;

            for (j = 0; j < N; j++)
            {
               if (val <= A[j] - S[j]) val = A[j] - S[j];
               B1[j+1] = val;
            }

            for (j = 1; j <= N; j++)
                A[j] = MAX( A[j-1], B1[j] + S[j]);
     }

     for (i = 1; i <= N; i++) Sol = MAX(Sol, A[i] + S[N] - S[i]);

     if ( Sol < 0 )   printf("0\n");
               else   printf("%d\n", Sol);


     fclose(stdin);
     fclose(stdout);
     return 0;
}