#include <cstdio>
#include <algorithm>

#define MAXN 10000
#define MAXK 1000

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

int main(){
    FILE *fin, *fout;
    fin=fopen("ferma.in", "r");
    fout=fopen("ferma.out", "w");

    int n, k;
    fscanf(fin, "%d%d", &n, &k);

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

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

    int ans=std::max(0, d[k][n]);

    for(int i=1; i<=n; i++)
        d[1][i]=std::max(d[1][i-1], s[i]);

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

    for(int i=k; i<=n; i++)
        ans=std::max(ans, d[k][i]+s[n]-s[i]);

    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}