#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 -1;
if (lstart + ceil((double)d / 2.0) > n)
{
int cres = 0;
for (int i = lstart; i < n; i++) cres += attraction[i];
return cres;
}
multiset<int> used;
int cres = 0;
int pos;
for (pos = lstart; pos < lstart + ceil((double)d / 2.0); pos++)
{
cres += attraction[pos];
used.insert(attraction[pos]);
}
if (d % 2)
{
cres -= *used.begin();
used.erase(used.begin());
}
int mmax = cres;
for (; pos < n; pos++)
{
if (used.size() < 2) break;
cres -= *used.begin();
used.erase(used.begin());
cres -= *used.begin();
used.erase(used.begin());
cres += attraction[pos];
used.insert(attraction[pos]);
mmax = max(mmax, cres);
}
return mmax;
}
int solve()
{
int mmax = 0;
for (int i = 0; i < n; i++)
{
mmax = max(mmax, findMaxAttr(i, totd - abs((start - i))));
}
return mmax;
}
};
int findMaxAttraction(signed n, signed start, signed d, signed attraction[])
{
Attractions at;
at.n = n;
at.start = start;
at.totd = d;
for (int i = 0; i < n; i++)
{
at.attraction.push_back(attraction[i]);
}
return at.solve();
}
