#include <vector>
#include <algorithm>
using namespace std;
struct SegmentTree {
vector<int> sortedAttractions;
vector<long long> prefixSum;
SegmentTree(vector<int> attractions) {
sort(attractions.begin(), attractions.end(), greater<int>());
sortedAttractions = attractions;
prefixSum.resize(sortedAttractions.size() + 1, 0);
for (int i = 0; i < sortedAttractions.size(); ++i) {
prefixSum[i + 1] = prefixSum[i] + sortedAttractions[i];
}
}
long long query(int k) {
if (k >= prefixSum.size()) return prefixSum.back();
return prefixSum[k];
}
};
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
if (d == 0) return 0;
vector<int> left, right;
for (int i = start - 1; i >= 0; --i) left.push_back(attraction[i]);
for (int i = start + 1; i < n; ++i) right.push_back(attraction[i]);
SegmentTree leftTree(left), rightTree(right);
long long maxAtt = attraction[start];
for (int a = 0; a <= left.size(); ++a) {
for (int dir = 0; dir < 2; ++dir) {
int cost = 2 * a + (dir ? 2 : 3) * 0;
if (cost + 1 > d) continue;
int remDays = d - cost - 1;
int maxB = remDays / (dir ? 2 : 3);
maxB = min(maxB, (int)right.size());
maxAtt = max(maxAtt, attraction[start] + leftTree.query(a) + rightTree.query(maxB));
}
}
for (int b = 0; b <= right.size(); ++b) {
for (int dir = 0; dir < 2; ++dir) {
int cost = 2 * b + (dir ? 2 : 3) * 0;
if (cost + 1 > d) continue;
int remDays = d - cost - 1;
int maxA = remDays / (dir ? 2 : 3);
maxA = min(maxA, (int)left.size());
maxAtt = max(maxAtt, attraction[start] + rightTree.query(b) + leftTree.query(maxA));
}
}
return maxAtt;
}
