#include"holiday.h"
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < ((int) n); i++)
#define all(a) a.begin(), a.end()
using namespace std;
int brute(int n, int start, int d, vector<int>x)
{
int maxx=0;
rep(i,n)
{
for(int j = i; j < n; j++)
{
priority_queue<int>pq;
for(int k = i; k <= j; k++)
{
pq.push(x[k]);
}
int sum = 0;
rep(b,(d-min(abs(start-i),abs(j-start))-abs(i-j))) if(pq.size()){sum+=pq.top(); pq.pop();}
maxx=max(sum,maxx);
}
}
return maxx;
}
int brute2(int n, int start, int d, vector<int>x)
{
int maxx = 0;
rep(cs,n)
{
if(n>3000&&cs) break;
int sum = 0;
priority_queue<int, vector<int>, greater<int>>pq;
for(int i = cs; i < n; i++)
{
sum+=x[i];
pq.push(x[i]);
int mamds=d-abs(cs-start)-abs(i-cs);
while (pq.size()&&((int)pq.size())>d-abs(cs-start)-abs(i-cs)) {sum-=pq.top(); pq.pop();}
maxx=max(sum,maxx);
}
}
return maxx;
}
int findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
vector<int>x(n);
rep(i,n) x[i] = attraction[i];
// if(n<=20) return brute(n,start,d,x);
int maxx = brute2(n,start,d,x);
reverse(all(x));
return max(maxx, brute2(n,n-start-1,d,x));
}
