#include"holiday.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
struct Attractions
{
int n, totd;
int start;
vector<int> attraction;
int findMaxAttr(int lstart, int d)
{
if (d <= 0) return 0;
multiset<int> active;
int cres = 0;
int pos;
for (pos = lstart; pos < lstart + d/2; pos++)
{
if (pos >= n) return cres;
cres += attraction[pos];
active.insert(attraction[pos]);
}
if (pos == n) return cres;
if (d % 2)
{
cres += attraction[pos];
active.insert(attraction[pos]);
pos++;
}
/*for (int i : active) cerr << i << " ";
cerr << "\n";
cerr << pos << "\n";*/
if (d % 2 == 0)
{
cres += attraction[pos];
active.insert(attraction[pos]);
cres -= *active.begin();
active.erase(active.begin());
pos++;
}
int mmax = cres;
for (; pos < n; pos++)
{
if (active.size() < 1) break;
cres += attraction[pos];
active.insert(attraction[pos]);
cres -= *active.begin();
active.erase(active.begin());
cres -= *active.begin();
active.erase(active.begin());
mmax = max(mmax, cres);
}
return mmax;
}
int solve()
{
int mmax = 0;
for (int i = 0; i <= start; i++)
{
mmax = max(mmax, findMaxAttr(i, totd - start + i));
}
if (start == 0) return mmax;
reverse(attraction.begin(), attraction.end());
start = n - start - 1;
for (int i = 0; i <= start; i++)
{
mmax = max(mmax, findMaxAttr(i, totd - start + i));
}
return mmax;
}
};
int findMaxAttraction(signed n, signed start, signed d, signed attraction[])
{
Attractions at;
at.n = n;
at.start = start + n;
at.totd = d;
for (int i = 0; i < n; i++)
{
at.attraction.push_back(attraction[i]);
}
return at.solve();
}
