#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll dp[N], opt[N];
int tab[N];
int n, s, d;
multiset<int> S;//S-dobre, S2-reszta
ll sum=0;
void solve(int l, int r){
opt[l]=l;
for(int i=opt[l]; i<=r; i++){
S.insert(tab[i]);
sum=0;
auto it=S.crbegin();
int j=0;
while(j<d+2*l-s-i && it!=S.crend()){
sum+=*it;
j++;
it++;
}
//cout<<l<<" "<<i<<" "<<j<<"\n";
if(sum>dp[l]){
opt[l]=i;
dp[l]=sum;
}
}
S.clear();
}
long long int findMaxAttraction(int _n, int start, int _d, int attraction[]) {
n=_n;
d=_d;
s=start;
for(int i=0; i<n; i++)tab[i]=attraction[i];
for(int i=0; i<=s; i++)solve(i, n-1);
ll ans=0;
for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
for(int i=0; i<n; i++)tab[i]=attraction[n-1-i];
for(int i=0; i<n; i++)dp[i]=opt[i]=0;
s=n-1-s;
for(int i=0; i<=s; i++)solve(i, n-1);
for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
return ans;
}
