#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, d, s;
int a[N], val[N];
long long int findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
n = n_;
d = d_;
s = start_;
for (int i = 0; i < n; ++i) {
a[i] = attraction[i];
}
long long cur = 0;
multiset<int> se;
auto add = [&](int x) {
se.insert(x);
cur += x;
};
auto Shrink = [&](int sz) {
while ((int) se.size() > sz) {
cur -= *se.begin();
se.erase(se.begin());
}
};
long long ans = 0;
for (int i = s; i >= 0; --i) {
for (int j = s - 1; j >= i; --j) {
add(a[j]);
}
int dis = s - i;
for (int j = s; j < n; ++j) {
int dis2 = j - s;
if (2 * dis + dis2 >= d) {
break;
}
add(a[j]);
Shrink(d - (2 * dis + dis2));
ans = max(ans, cur);
}
cur = 0;
se.clear();
}
//for (int i = s; i < n; ++i) {
//for (int j = s; j <= i; ++j) {
//add(a[j]);
//}
//int dis = i - s;
//for (int j = s; j >= 0; --j) {
//int dis2 = s - j;
//if (2 * dis + dis2 > d) {
//break;
//}
//add(a[j]);
//Shrink(d - (2 * dis + dis2));
//ans = max(ans, cur);
//}
//cur = 0;
//se.clear();
//}
return ans;
}
