#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct DS{
priority_queue<ll,vector<ll>,greater<ll>> pq;
ll sum = 0;
DS(){
sum = 0;
}
void init(){
sum = 0;
while(!pq.empty())pq.pop();
}
void add(ll k){
pq.push(k);
sum += k;
}
void shape(int len){
while(!pq.empty()&&(ll)pq.size()>len){
sum -= pq.top();
pq.pop();
}
assert(pq.empty()||pq.size()<=len);
return;
}
};
namespace ZERO{
const ll mxn = 1e5+10;
DS ds;
ll GO(int n,int s,int d,int arr[]){
ds.init();
ll ans = 0;
for(int i = 0;i<=min(d,n-1);i++){
ds.add(arr[i]);
int rest = d-i;
ds.shape(d-i);
ans = max(ans,ds.sum);
}
return ans;
}
}
namespace BRUTE{
const ll mxn = 3030;
ll tr1[mxn],tr2[mxn];
ll arr[mxn];
DS ds;
int n,s,d;
ll calc(int e){
ll re = 0;
ds.init();
for(int i = e;i>s;i--)ds.add(arr[i]);
ll tans = 0;
for(int i = s;i>=0;i--){
ds.add(arr[i]);
int rest = d-((e-s)*2+(s-i));
ds.shape(rest);
//cerr<<"L FIRST: "<<i<<' '<<e<<"::"<<rest<<','<<ds.pq.size()<<','<<ds.sum<<endl;
if(tans<ds.sum){
tans = ds.sum;
tr1[e] = i;
}
}
re = max(re,tans);
ds.init();
tans = 0;
for(int i = e;i>s;i--)ds.add(arr[i]);
for(int i = s;i>=0;i--){
ds.add(arr[i]);
int rest = d-((e-s)+(s-i)*2);
ds.shape(rest);
if(tans<ds.sum){
tans = ds.sum;
tr2[e] = i;
}
}
re = max(re,tans);
return re;
}
ll GO(int nn,int ss,int dd,int tarr[]){
n = nn,s = ss,d = dd;
for(int i = 0;i<n;i++)arr[i] = tarr[i];
ll ans = 0;
for(int i = s;i<min(s+d,n);i++)ans = max(ans,calc(i));
return ans;
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
/*
auto t1 = BRUTE::GO(n,start,d,attraction),t2 = ZERO::GO(n,start,d,attraction);
cerr<<t1<<','<<t2<<endl;
assert(t1 == t2);
*/
if(start == 0)return ZERO::GO(n,start,d,attraction);
else return BRUTE::GO(n,start,d,attraction);
}
