#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;
int v[N], sum[N];
int d[N][K][2];

void init(int k)
{
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            d[i][j][1] = d[i][j][0] = -INF;
}

void dinamica(int k)
{
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= k; ++j) {
            d[i + 1][j][0] = max(d[i + 1][j][0], d[i][j][1]);
            d[i + 1][j][1] = max(d[i + 1][j][1], d[i][j][1] + v[i]);
            d[i + 1][j + 1][1] = max(d[i + 1][j + 1][1], d[i][j][1] + v[i]);

            d[i + 1][j][0] = max(d[i + 1][j][0], d[i][j][0]);
            d[i + 1][j + 1][1] = max(d[i + 1][j + 1][1], d[i][j][0] + v[i]);
        }
}

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[n][k][0], d[n][k][1]);
    init(k + 1);
    d[1][1][1] = v[1];
    dinamica(k + 1);
    rez2 = d[n][k + 1][1];
    printf("%d\n", d[5][2][0]);
    printf("%d", max(rez1, rez2));
}