#include"holiday.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
pair<long long,long long> aib[nmax];
long long ans;
pair<int,int> norm[nmax];
int wh[nmax],v[nmax];
int n,D;
inline int lbit(int x)
{
return ((x^(x-1))&x);
}
void update(int poz,long long v1,long long v2)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx].first+=v1,aib[idx].second+=v2;
}
long long find_kth(int k)
{
int cat=0,poz=0;
long long ret=0;
for(int p=17;p>=0;p--)
{
if(poz+(1<<p)<=n&&cat+aib[poz+(1<<p)].first<=k)
{
poz+=(1<<p);
cat+=aib[poz].first;
ret+=aib[poz].second;
}
}
return ret;
}
void add(int poz)
{
update(wh[poz],1,v[poz]);
}
void rem(int poz)
{
update(wh[poz],-1,-v[poz]);
}
void qr(int st,int dr,int m)
{
ans=max(ans,find_kth(D-2*(dr-m)-(m-st)));
}
void solve(int s)
{
for(int i=s;i<=n;i++)
{
add(i);
qr(s,i,s);
for(int j=s-1;j>=1;j--)
{
add(j);
qr(j,i,s);
}
for(int j=s-1;j>=1;j--)
rem(j);
}
for(int i=s;i<=n;i++)
rem(i);
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n=N;
for(int i=1;i<=n;i++)
v[i]=attraction[i-1];
for(int i=1;i<=n;i++)
norm[i].first=v[i],norm[i].second=i;
sort(norm+1,norm+n+1);
for(int i=1;i<=n;i++)
wh[norm[i].second]=n-i+1;
D=d;
start++;
solve(start);
for(int i=1;i<=n/2;i++)
swap(v[i],v[n-i+1]),swap(wh[i],wh[n-i+1]);
solve(n-start+1);
return ans;
}
