#include <fstream>

using namespace std;

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

const int INF = 1000000000;

int n,k;
int v[10005];

int main()
{
    fin >> n >> k;
    int d[n + 5][k + 5][2];
    for(int i = 1; i <= n; ++i){
        fin >> v[i];
    }
    d[1][0][0] = 0;
    d[1][0][1] = -INF;
    d[1][1][0] = -INF;
    d[1][1][1] = v[1];
    for(int i = 2; i <= n; ++i){
        d[i][0][0] = 0;
        d[i][0][1] = 0;
        for(int j = 1; j <= i; ++j){
            if(j == i){
                d[i][j][0] = -INF;
                d[i][j][1] = d[i - 1][j][1] + v[i];
                continue;
            }
            d[i][j][0] = max(d[i - 1][j][0], d[i - 1][j][1]);
            d[i][j][1] = max(max(d[i - 1][j][1], d[i - 1][j - 1][0]),  d[i - 1][j - 1][1]) + v[i];
        }
    }
    int ans = max(max(d[n][k][0], d[n][k][1]), 0);
    d[1][0][0] = -INF;
    d[1][0][1] = -INF;
    d[1][1][0] = -INF;
    d[1][1][1] = v[1];
    for(int i = 2; i <= n; ++i){
        d[i][0][0] = 0;
        d[i][0][1] = 0;
        for(int j = 1; j <= i; ++j){
            if(j == 1){
                d[i][j][0] = max(d[i - 1][j][0], d[i - 1][j][1]);
                d[i][j][1] = -INF;
                continue;
            }
            if(j == i){
                d[i][j][0] = -INF;
                d[i][j][1] = d[i - 1][j - 1][1] + v[i];
            }
            else{
                d[i][j][0] = max(d[i - 1][j][0], d[i - 1][j][1]);
                d[i][j][1] = max(max(d[i - 1][j][1], d[i - 1][j - 1][0]),  d[i - 1][j - 1][1]) + v[i];
            }
        }
    }
    int s = 0;
    for(int i = n; i >= k; --i){
        s += v[i];
        if(i == k){
            ans = max(ans, d[i - 1][k][1] + s);
        }
        else{
            ans = max(ans, max(d[i - 1][k][0], d[i - 1][k][1]) + s);
        }
    }
    fout << ans;
    return 0;
}