#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long all[maxn],n,st,k;
long long mainres=0;
void solve(long long l,long long r,long long tl,long long tr){
if(l>r){
return ;
}
long long mid=(l+r)>>1,opt=tl,mx=-1;
for(long long i=tl;i<=tr;i++){
priority_queue<long long>pq;
for(long long j=i;j<=mid;j++){
pq.push(all[j]);
}
long long ted=k-(mid-i+min(mid-st,st-i));
if(ted>=0){
long long fake=0;
for(long long j=0;(long long)pq.size()>0&&j<ted;j++){
fake+=(pq.top());
pq.pop();
}
// cout<<i<<" "<<mid<<" "<<ted<<" "<<fake<<endl;
if(fake>mx){
opt=i;
mx=fake;
}
}
}
// cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<opt<<" "<<mx<<" "<<mid<<endl;
mainres=max(mainres,mx);
solve(l,mid-1,tl,opt);
solve(mid+1,r,opt,tr);
}
long long findMaxAttraction(int N, int start, int d, int attraction[]) {
n=N;
st=start;
k=d;
st++;
for(long long i=1;i<=n;i++){
all[i]=attraction[i-1];
}
solve(st,n,1,st);
return mainres;
}
