#include <bits/stdc++.h>
using namespace std;
const int N = 4e3;
int a[N];
long long f[N][N][3];
int main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    // freopen("a.out", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    int n, b;
    cin >> n >> b;
    memset(f, -1, sizeof f);
    f[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        f[i][0][0] = f[i - 1][0][0];
        for (int j = 1; j <= min(i, b); ++j) {
            f[i][j][0] = *max_element(f[i - 1][j], f[i - 1][j] + 3);
            f[i][j][1] = f[i - 1][j - 1][0];
            if (f[i - 1][j - 1][2] != -1 || f[i - 1][j - 1][1] != -1)
                f[i][j][2] = max(f[i - 1][j - 1][2], f[i - 1][j - 1][1]) + a[i];
        }
    }
    long long ans = *max_element(f[n][b], f[n][b] + 3);

    memcpy(f[0], f[n], sizeof(f[n]));
    for (int i = 1; i <= n; ++i) {
        f[i][0][0] = f[i - 1][0][0];
        for (int j = 1; j <= b; ++j) {
            f[i][j][0] = *max_element(f[i - 1][j], f[i - 1][j] + 3);
            f[i][j][1] = f[i - 1][j - 1][0];
            if (f[i - 1][j - 1][2] != -1 || f[i - 1][j - 1][1] != -1)
                f[i][j][2] = max(f[i - 1][j - 1][2], f[i - 1][j - 1][1]) + a[i];
        }
    }
    cout << max(ans, *max_element(f[n][b], f[n][b] + 3)) << "\n";
}