#if 1
#pragma GCC optimize "O3"
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <random>
#include <cassert>
#include <cmath>
#include <cstring>
#include <chrono>
using namespace std;
using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using f32 = float; using f64 = double;
template <class T> inline T sq(T a) { return a * a; }
template <class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } return false; }
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
void _u() { cerr << endl; } template <class H, class... T> void _u(H&& h, T&&... t) { cerr << h << ", "; _u(move(t)...); }
#define _polyfill(v) v
#define _overload3(a, b, c, d, ...) d
#define _rep3(i, a, b) for (i32 i = i32(a); i < i32(b); ++i)
#define _rep2(i, b) _rep3(i, 0, b)
#define _rep1(i) for (i32 i = 0; ; ++i)
#define rep(...) _polyfill(_overload3(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__))
#define A(a) begin(a), end(a)
#define S(a) i32((a).size())
#define U(...) { cerr << #__VA_ARGS__ << ": "; _u(__VA_ARGS__); }
#define lin U(__LINE__)
#define exi exit(0);
#endif

class timer {
    vector<timer> timers;
    int n = 0;
public:
    double limit = 2.95;
    double t = 0;
    timer() {}
    timer(int size) : timers(size) {}
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(char id) {
        timers[id].measure();
    }
    void print() {
        if (n % 2)
            measure();
        for (int i = 0; i < 128; ++i) {
            if (timers[i].n)
                cerr << (char)i << ' ' << timers[i].t << 's' << endl;
        }
        cerr << "  " << t << 's' << endl;
    }
    static double time() {
#ifdef LOCAL
        return __rdtsc() / 3.3e9;
#else
        using namespace std::chrono;
        return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count() / 1000.0;
#endif
    }
} timer(128);

constexpr bool Deterministic = 0;
class rando {
    unsigned y;
public:
    rando(unsigned y) : y(y) {}
    unsigned next() {
        return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
    }
    int next(int b) {
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double nextDouble(double b = 1) {
        return b * next() / 4294967296.0;
    }
    double nextDouble(double a, double b) {
        return nextDouble(b - a) + a;
    }
    int operator() (int b) {
        return next(b);
    }
} rando(Deterministic ? 2463534242 : random_device()());

i32 main() {
    i32 n, k;
    while (cin >> n >> k) {
        vector<i32> V(n);
        for (i32& v : V) cin >> v;
        i64 sm0 = 0, sm1 = 0;
        vector<i64> a0, a1, a2, a3;
        a0.clear();
        i64 mx = -1ll << 62;
        rep (l, min(n + 1, k + 1)) {
            sm1 = 0;
            a1.clear();
            rep (r, min(n + 1 - l, k + 1 - l)) {
                a2.assign(A(a0));
                a2.insert(a2.end(), A(a1));
                sort(A(a2));
                a3.assign(S(a2) + 1, 0);
                rep (i, S(a2)) {
                    a3[i + 1] = a3[i] + a2[i];
                }
                rep (d, min(S(a2) + 1, k + 1 - l - r)) {
                    chmax(mx, sm0 + sm1 + a3.back() - a3[d]);
                }
                if (V[S(V) - 1 - r] > 0) {
                    sm1 += V[S(V) - 1 - r];
                } else if (V[S(V) - 1 - r] < 0) {
                    a1.emplace_back(V[S(V) - 1 - r]);
                }
            }
            if (V[l] > 0) {
                sm0 += V[l];
            } else if (V[l] < 0) {
                a0.emplace_back(V[l]);
            }
        }
        cout << mx << endl;
    }
    return 0;
}


Measured memory_bytes: 256