#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e4+10, maxk = 2e2+10, inf = 1e15;

ifstream fin("monkeys.in");
ofstream fout("monkeys.out");

int n, k;
int dp[maxn][maxk], dp_left[maxn][maxk], dp_right[maxn][maxk], a[maxn], prefix[maxn];
int opt_left[maxn][maxk];
int opt_right[maxn][maxk];

void f_left(int ix, int currk, int l_border, int r_border) {

    l_border = max(l_border, ix+1);
    r_border = min(r_border, n-2*(currk-1));
    int sum = prefix[l_border-1] - prefix[ix-1] - 2*a[ix];
    opt_left[ix][currk] = -1;

    // cout << "f_left: " << ix << ' ' << currk << ' ' << l_border << ' ' << r_border << '\n';

    for (int i = l_border ; i <= r_border ; ++i) {

        sum += a[i];
        if (sum < 0) continue;
        if (dp_left[ix][currk] < sum + dp[i+1][currk-1]) {

            dp_left[ix][currk] = sum + dp[i+1][currk-1];
            opt_left[ix][currk] = i;

        }

    }

    // cout << "res: " << dp_left[ix][currk] << ' ' << opt_left[ix][currk] << '\n';

}

void f_right(int ix, int currk, int l_border, int r_border) {

    l_border = max(l_border, ix+1);
    r_border = min(r_border, n-2*(currk-1));
    int sum = prefix[l_border-2] - prefix[ix-1];
    opt_right[ix][currk] = -1;

    // cout << "f_right: " << ix << ' ' << currk << ' ' << l_border << ' ' << r_border << '\n';

    for (int i = l_border ; i <= r_border ; ++i) {

        sum += a[i-1];
        if (sum - a[i] < 0) continue;
        if (dp_right[ix][currk] < sum - a[i] + dp[i+1][currk-1]) {

            dp_right[ix][currk] = sum - a[i] + dp[i+1][currk-1];
            opt_right[ix][currk] = i;

        }

    }

    // cout << "res: " << dp_right[ix][currk] << ' ' << opt_right[ix][currk] << '\n';

}

void calc_left(int l, int r, int l_border, int r_border, int currk) {

    if (l == r) {

        f_left(l, currk, l_border, r_border);
        return;

    }

    int mid = (l+r)/2;
    f_left(mid, currk, l_border, r_border);
    if (l <= mid-1) calc_left(l, mid-1, l_border, (opt_left[mid][currk] == -1 ? r_border : opt_left[mid][currk]), currk);
    if (mid+1 <= r) calc_left(mid+1, r, (opt_left[mid][currk] == -1 ? l_border : opt_left[mid][currk]), r_border, currk);

}

void calc_right(int l, int r, int l_border, int r_border, int currk) {

    if (l == r) {

        f_right(l, currk, l_border, r_border);
        return;

    }

    int mid = (l+r)/2;
    f_right(mid, currk, l_border, r_border);
    if (l <= mid-1) calc_right(l, mid-1, l_border, (opt_left[mid][currk] == -1 ? r_border : opt_left[mid][currk]), currk);
    if (mid+1 <= r) calc_right(mid+1, r, (opt_left[mid][currk] == -1 ? l_border : opt_left[mid][currk]), r_border, currk);

}

void solve() {

    for (int i = 0 ; i < maxn ; ++i) {
    
        fill(dp[i], dp[i]+maxk, -inf);
        fill(dp_left[i], dp_left[i]+maxk, -inf);
        fill(dp_right[i], dp_right[i]+maxk, -inf);
    
    }

    k /= 2;
    for (int i = 1 ; i <= n ; ++i)
        prefix[i] = prefix[i-1] + a[i];

    dp[n+1][0] = 0;
    for (int i = 1 ; i <= k ; ++i) {

        // cout << "calc: " << i << "\n";

        calc_left(1, n, 1, n, i);

        // cout << "\n\n";

        calc_right(1, n, 1, n, i);

        for (int j = 1 ; j <= n ; ++j)
            dp[j][i] = max(dp_left[j][i], dp_right[j][i]);

    }

    fout << dp[1][k] << '\n';

}

void fast_io() {
 
    ios_base :: sync_with_stdio(0);
    fin.tie(nullptr);
    fout.tie(nullptr);
 
}

void read() {
 
    fin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
        fin >> a[i];
 
}
 
signed main () {
 
    fast_io();
    read();
    solve();
 
    return 0;
 
}