#include<fstream>
#define DIM 10005
using namespace std;
int n, k, i, j, sol, ii, maxim, maxim1;
int v[DIM], s[DIM];
int d[2][DIM], e[2][DIM];
ifstream fin("ferma.in");
ofstream fout("ferma.out");
int main(){
    fin>> n >> k;
    for(i = 1; i <= n; i++){
        fin>> v[i];
        s[i] = s[i - 1] + v[i];
        e[0][i] = max(s[i], e[0][i - 1]);
    }
    ii = 0;
    for(i = 1; i <= k; i++){
        maxim = maxim1 = 0;
        for(j = 1; j <= n; j++){
            d[ii][j] = max(d[ii][j - 1], maxim + s[j]);
            maxim = max(maxim, d[1 - ii][j] - s[j]);
        }
        if(i != 1){
            for(j = 1; j <= n; j++){
                e[ii][j] = max(e[ii][j - 1], maxim1 + s[j]);
                maxim1 = max(maxim1, e[1 - ii][j] - s[j]);
            }
        }
        ii = 1 - ii;
    }
    sol = 0;
    for(i = 1; i <= n; i++){
        sol = max(sol, d[1 - ii][i]);
        sol = max(sol, e[1 - ii][i] + s[n] - s[i]);
    }
    fout<< sol <<"\n";
    return 0;
}