#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 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 dorg=d;
int maxx = 0;
for(int mat = 0; mat <= 100; mat++){
int sum = 0;
int i = 0;
while(i<n&&d>=1)
{
if(x[i]>=mat) {
sum+=x[i];
d--;
}
d--;
i++;
}
d=dorg;
maxx=max(maxx,sum);
}
// assert(maxx==brute(n,start,dorg,x));
return maxx;
}
