#include <cstdio>

const int N = 20005, INF = 2000000000;

int n, k, v[N], a[2][N], b[2][N], poza[2][N], pozb[2][N];

void read() {
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
}

inline int max(int x, int y) {
    return x > y ? x : y;
}

int ssm(int ps,int pf) {
    int sc = v[ps], st = 0;
    if (sc > st)
        st = sc;
    for (int i = ps + 1; i <= pf; ++ i) {
        sc += v[i];
        if (sc > st)
            st = sc;
    }
    return st;
}

void solve() {
    a[1][1] = 1;
    poza[1][1] = 1;
    b[1][1] = -INF;
    pozb[1][1] = 0;

    for (int j = 2; j <= n; ++ j) {
        if (a[1][j - 1] + v[j] > v[j])
            a[1][j] = a[1][j - 1] + v[j], poza[1][j] = poza[1][j - 1];
        else if (a[1][j - 1] + v[j] < v[j])
            a[1][j] = v[j], poza[1][j] = j;
        else
            a[1][j] = v[j], poza[1][j] = max(poza[1][j - 1], j);

        if (a[1][j - 1] > b[1][j - 1])
            b[1][j] = a[1][j - 1], pozb[1][j] = poza[1][j - 1];
        else if (a[1][j - 1] < b[1][j - 1])
            b[1][j] = b[1][j - 1], pozb[1][j] = pozb[1][j - 1];
        else
            b[1][j] = b[1][j - 1], pozb[1][j] = max(poza[1][j - 1], pozb[1][j - 1]);
    }
    for (int i = 2; i <= k; ++ i)
        for (int j = 1; j <= n; ++ j) {
            if (a[i & 1][j - 1] + v[j] > b[(i - 1) & 1][j - 1] + v[j])
                a[i & 1][j] = a[i & 1][j - 1] + v[j], poza[i & 1][j] = poza[i & 1][j - 1];
            else if (a[i & 1][j - 1] + v[j] < b[(i - 1) & 1][j - 1] + v[j])
                a[i & 1][j] = b[(i - 1) & 1][j - 1] + v[j], poza[i & 1][j] = pozb[(i - 1) & 1][j - 1];
            else
                a[i & 1][j] = b[(i - 1) & 1][j - 1] + v[j], poza[i & 1][j] = max(poza[i & 1][j - 1], pozb[(i - 1) & 1][j - 1]);

            if (a[i & 1][j - 1] > b[i & 1][j - 1])
                b[i & 1][j] = a[i & 1][j - 1], pozb[i & 1][j] = poza[i & 1][j - 1];
            else if (a[i & 1][j - 1] < b[i & 1][j - 1])
                b[i & 1][j] = b[i & 1][j - 1], pozb[i & 1][j] = pozb[i & 1][j - 1];
            else
                b[i & 1][j] = b[i & 1][j - 1], pozb[i & 1][j] = max(poza[i & 1][j - 1], pozb[i & 1][j - 1]);
        }
    printf("%d\n", max(a[k & 1][n] + ssm( 1, poza[k & 1][n] - 1), b[k & 1][n]));
}

int main() {
    read();
    solve();
    return 0;
}