#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf -2000000002
#define Nmax 10002
#define Kmax 1002
using namespace std;
int n, i, j, k, v[Nmax], maxv, Mv[Nmax];
int a[2][Nmax], b[2][Nmax], s[Nmax];
int main()
{
    int sol = 0, sum, p, q, j;
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);
    scanf("%d %d", &n, &k);
    maxv = inf;
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]),
        s[i] = s[i - 1] + v[i];
    //++ k;
    for (i = 1; i <= k; ++ i)
        for (j = 1; j <= n; ++ j)
        {
            a[i & 1][j] = max(a[i & 1][j - 1], maxv + s[j]);
            maxv = max(a[(i - 1) & 1][j] - s[j], maxv);
        }
    sol = a[k & 1][n];
    a[1][0] = inf;
    for (j = 1; j <= n; ++ j)
        a[1][j] = max(s[j], a[1][j - 1]);

    maxv = inf;
    for (i = 2; i <= k; ++ i)
        for (j = 1; j <= n; ++ j)
        {
            a[i & 1][j] = max(a[i & 1][j - 1], maxv + s[j]);
            maxv = max(a[(i - 1) & 1][j] - s[j], maxv);
        }

    for (i = k; i < n; ++ i)
        maxv = max(maxv, a[k & 1][i] - s[i]);

    a[(k + 1) & 1][n] = s[n] + maxv;

    sol = max(sol, a[(k + 1) & 1][n]);
    printf("%d", sol);
    return 0;
}