#include <cstdio>
#define MAXN 10000
#define MAXK 1000

int ans, d[MAXK+1][MAXN+1], s[MAXN+1];

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

int main()
{
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);

    int n, k, i, j, best, x;

    scanf("%d%d", &n, &k);

    for(i=1; i<=n; ++i){
        scanf("%d", &x);
        s[i] = s[i-1] + x;
    }

    for(i=1; i<=k; ++i)
    {
        best = d[i-1][i-1] - s[i-1];
        for(j=i; j<=n; ++j)
        {
            d[i][j] = maxim(d[i][j-1], s[j] + best);
            best = maxim(best, d[i-1][j] - s[j]);
        }
    }

    ans = maxim(ans, d[k][n]);

    d[1][1] = s[1];
    for(i=2; i<=n; ++i)
        d[1][i] = maxim(d[1][i-1], s[i]);

    for(i=2; i<=k; ++i)
    {
        best = d[i-1][i-1] - s[i-1];
        for(j=i; j<=n; ++j)
        {
            d[i][j] = maxim(d[i][j-1], s[j] + best);
            best = maxim(best, d[i-1][j] - s[j]);
        }
    }

    for(i=k; i<=n; ++i)
        ans = maxim(ans, d[k][i] + s[n] - s[i]);

    printf("%d", ans);

    return 0;
}