#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
ll findMaxAttraction(int n, int start, int d, int a[]){
ll ans = 0;
multiset<int> st;
ll sm = 0;
for (int i = start; i < n; i ++){
int att = d - i + start;
if (att <= 0) break;
st.insert(a[i]);
sm += a[i];
while (st.size() > att){
sm -= *st.begin();
st.erase(st.begin());
}
ans = max(ans, sm);
}
st.clear();
sm = 0;
for (int i = start; i >= 0; i --){
int att = d + i - start;
if (att <= 0) break;
st.insert(a[i]);
sm += a[i];
while (st.size() > att){
sm -= *st.begin();
st.erase(st.begin());
}
ans = max(ans, sm);
}
if (start != 0 and start != (n - 1)){
for (int l = 0; l < start; l ++){
st.clear();
sm = 0;
for (int r = l; r <= start; r ++)
st.insert(a[r]), sm += a[r];
for (int r = start + 1; r < n; r ++){
int att = d - 2 * (start - l) - (r - start);
if (att <= 0) break;
while (st.size() > 0){
sm -= *st.begin();
st.erase(st.begin());
}
ans = max(ans, sm);
}
}
for (int r = start + 1; r < n; r ++){
st.clear();
sm = 0;
for (int l = start; l <= r; l ++)
st.insert(a[l]), sm += a[l];
for (int l = start - 1; l >= 0; l --){
int att = d - 2 * (r - start) - (start - l);
if (att <= 0) break;
while (st.size() > 0){
sm -= *st.begin();
st.erase(st.begin());
}
ans = max(ans, sm);
}
}
}
return ans;
}
