#include <cassert>
#include <cstdio>
#include <cstring>
 
#include <algorithm>
using namespace std;
 
const int N = 10005;
const int K = 1005;
const int INF = 0x3f3f3f3f;
 
int n, k, rez1, rez2, l;
int v[N], sum[N];
int d[3][K][2];
 
void init(int k)
{
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            d[0][j][1] = d[0][j][0] = d[1][j][1] = d[1][j][0] = -INF;
}
 
void dinamica(int k)
{
    l = 0;
    for (int i = 0; i < n; ++i) {
        l = 1 - l;
        for (int j = 0; j <= k; ++j) {
            d[l][j][0] = max(d[l][j][0], d[1 - l][j][1]);
            d[l][j][1] = max(d[l][j][1], d[1 -l][j][1] + v[i + 1]);
            d[l][j + 1][1] = max(d[l][j + 1][1], d[1 - l][j][1] + v[i + 1]);
 
            d[l][j][0] = max(d[l][j][0], d[1 - l][j][0]);
            d[l][j + 1][1] = max(d[l][j + 1][1], d[1 - l][j][0] + v[i + 1]);
        }
        for (int j = 0; j <= k; ++j)
            d[1 - l][j][0] = d[1 - l][j][1] = -INF;
    }
}
 
int main()
{
    assert(freopen ("ferma.in", "r", stdin));
    assert(freopen ("ferma.out", "w", stdout));
 
    assert(scanf("%d %d", &n, &k) == 2);
    for (int i = 1; i <= n; ++i) {
        assert(scanf("%d", &v[i]) == 1);
    }
    
    init(k);
    d[0][0][0] = 0;
    dinamica(k);
    rez1 = max(d[l][k][0], d[l][k][1]);
    init(k + 1);
    d[1][1][1] = v[1];
    dinamica(k + 1);
    rez2 = d[l][k + 1][1];
    printf("%d", max(rez1, rez2));
}