#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if(start==0){
int64_t ans=0,cur=0;
multiset<int>tovis;
for(int i=0;i<n;i++){
cur+=attraction[i];
tovis.insert(attraction[i]);
while(d-i<tovis.size()){
cur-=*tovis.begin();
tovis.erase(tovis.begin());
}
ans=max(ans,cur);
}
return ans;
}
int64_t l[10*n],r[10*n],ll[10*n],rr[10*n];
memset(l,0,sizeof(l));
memset(ll,0,sizeof(l));
memset(r,0,sizeof(l));
memset(rr,0,sizeof(l));
multiset<int,greater<int>>tovis;
for(int i=start+1;i<n;i++){
tovis.insert(attraction[i]);
int cnt=0;
int64_t cur=0;
for(int j:tovis){
cnt++;
cur+=j;
r[i-start+cnt]=max(r[i-start+cnt],cur);
rr[(i-start)*2+cnt]=max(rr[(i-start)*2+cnt],cur);
}
}
tovis.clear();
for(int i=start-1;0<=i;i--){
tovis.insert(attraction[i]);
int cnt=0;
int64_t cur=0;
for(int j:tovis){
cnt++;
cur+=j;
l[start-i+cnt]=max(l[start-i+cnt],cur);
ll[(start-i)*2+cnt]=max(ll[(start-i)*2+cnt],cur);
}
}
int64_t ans=max({l[d],r[d],l[d-1]+attraction[start],r[d-1]+attraction[start]});
for(int i=0;i<d;i++){
ans=max({ans,l[i]+rr[d-i],ll[i]+r[d-i]});
if(i)ans=max({ans,l[i-1]+rr[d-i]+attraction[start],ll[i-1]+r[d-i]+attraction[start]});
}
return ans;
}
