#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
ll slv(int s, ll a[], int d, int x, int n){
multiset <ll> st;
ll ss = 0;
ll mx = 0;
int cnt = 0;
for(int i = s; i < n; i++){
int x = d - (cnt);
cnt++;
st.insert(a[i]);
ss += a[i];
while((int)st.size() > x && !st.empty())
ss -= *st.begin(), st.erase(st.begin());
mx = max(mx, ss);
}
return mx;
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
ll a[n + 1];
for(int i = 0; i < n; i++)
a[i] = attraction[i];
if(start == 0){
multiset <ll> st;
ll s = 0;
ll mx = 0;
for(int i = 0; i < n; i++){
int x = d - i;
st.insert(a[i]);
s += a[i];
while((int)st.size() > x && !st.empty())
s -= *st.begin(), st.erase(st.begin());
mx = max(mx, s);
}
return mx;
}
else{
ll ans = 0;
for(int i = 0; i <= start; i++){
if(d < start - i) continue;
ll x = slv(i, a, d - (start - i), start, n);
ans = max(ans, x);
}
for(int i = 0; i < n; i++){
if(i < n - 1- i)
swap(a[i], a[n - 1 - i]);
}
start = n - start - 1;
for(int i = 0; i <= start; i++){
if(d < start - i) continue;
ll x = slv(i, a, d - start + i, start,n);
ans = max(ans, x);
}
return ans;
}
return 0;
}
