#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
long long int findFromZero(int n, int start, int d, int attraction[], int walkingFactor) {
assert(start == 0);
map<int, int> bestAttractions;
long long int res = 0;
long long int sum = 0;
int inUse = 0;
for (int i = 0; i<min(d, n); i++) {
sum += attraction[i]; bestAttractions[attraction[i]]++; inUse++;
while (i*walkingFactor + inUse > d) {
if (bestAttractions.empty()) return res;
sum -= (*bestAttractions.begin()).first; bestAttractions[(*bestAttractions.begin()).first]--; inUse--;
if (bestAttractions[(*bestAttractions.begin()).first] == 0) bestAttractions.erase((*bestAttractions.begin()).first);
}
// cerr << i << " " << inUse << "\n";
res = max(sum, res);
}
return res;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if (n > 3000) {
return findFromZero(n, start, d, attraction, 1);
}
vector<int> left;
vector<int> right;
for (int i = 0; i<n; i++) {
if (i<=start) left.push_back(attraction[i]);
if (i>start) right.push_back(attraction[i]);
}
reverse(left.begin(), left.end());
int attL[left.size()];
int attR[right.size()];
for (int i = 0; i<left.size(); i++) attL[i] = left[i];
for (int i = 0; i<right.size(); i++) attR[i] = right[i];
long long int res = 0;
for (int i = 0; i<=d; i++) {
long long int tmp = 0;
tmp += findFromZero(left.size(), 0, i, attL, 1);
tmp += findFromZero(right.size(), 0, d-i-2, attR, 2);
res = max(res, tmp);
tmp = 0;
tmp += findFromZero(left.size(), 0, i, attL, 2);
tmp += findFromZero(right.size(), 0, d-i-1, attR, 1);
res = max(res, tmp);
}
return res;
}
