#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005
typedef long long lo;
int st,dist;
int dizi[lim];
lo cev;
inline int cal(int x,int y){
int sol=abs(x-st);
int sag=abs(y-st);
return sol+sag+min(sol,sag);
}
inline void dnq(int l,int r,int optl,int optr){
if(l>r)return ;
int mi=(l+r)/2;
int opt=optl;
int best=-1;
for(int i=optl;i<=min(optr,mi);i++){
int git=cal(i,mi);
if(git>dist)continue;
int kalan=dist-git;
vector<lo> tut;
for(int o=i;o<=mi;o++)tut.pb((lo)dizi[o]);
sort(tut.rbegin(),tut.rend());
lo cur_cev=0;
for(int o=0;o<min(kalan,(int)tut.size());o++)cur_cev+=tut[o];
if(cur_cev>best){
best=cur_cev;
opt=i;
}
cev=max(cev,cur_cev);
}
dnq(l,mi-1,optl,opt),dnq(mi+1,r,opt,optr);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
st=start+1;
dist=d;
FOR{
dizi[i]=attraction[i-1];
}
dnq(st,n,1,st);
//~ for(int i=1;i<=st;i++){
//~ for(int j=st;j<=n;j++){
//~ int git=cal(i,j);
//~ if(git>d)continue;
//~ int kalan=d-git;
//~ vector<lo> tut;
//~ for(int o=i;o<=j;o++)tut.pb((lo)dizi[o]);
//~ sort(tut.rbegin(),tut.rend());
//~ lo cur_cev=0;
//~ for(int o=0ll;o<min(kalan,tut.size());o++)cur_cev+=tut[o];
//~ cev=max(cev,cur_cev);
//~ }
//~ }
return cev;
}
//~ int main(){
//~ faster
//~ int n,start,d;
//~ cin>>n>>start>>d;
//~ int arr[n];
//~ FOR{
//~ cin>>arr[i-1];
//~ }
//~ lo cev=findMaxAttraction(n,start,d,arr);
//~ cout<<cev<<'\n';
//~ return 0;
//~ }
