#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long int findMaxAttraction(int n, int s, int d, int attraction[]) {
vector<ll> v(attraction, attraction + n);
vector<ll> a1,a2;
for(ll &x: v) cin>>x;
for(ll i=s;i>=0;i--){
a1.push_back(v[i]);
}
for(ll i=s;i<n;i++){
a2.push_back(v[i]);
}
ll l=4*n;
vector<vector<ll>>dp1(a1.size(),vector<ll>(l,-1));
vector<vector<bool>>nd1(a1.size(),vector<bool>(l,0));
dp1[0][0]=0;
dp1[0][1]=v[s];
nd1[0][0]=0;
nd1[0][1]=1;
ll b=0,f=1;
for(ll i=1;i<a1.size();i++){
for(ll j=b;j<=f;j++){
if(dp1[i-1][j]+a1[i]>dp1[i][j+2]){
nd1[i][j+2]=nd1[i-1][j];
}
if(dp1[i-1][j]>dp1[i][j+1]){
nd1[i][j+1]=nd1[i-1][j];
}
dp1[i][j+2]=max(dp1[i][j+2], dp1[i-1][j]+a1[i]);
dp1[i][j+1]=max(dp1[i][j+1], dp1[i-1][j]);
}
b=b+1;
f=f+2;
}
vector<ll>k1(f+1,-1);
vector<ll>v1(f+1,-1);
vector<bool>n1(f+1,false);
b=1,f=3;
k1[0]=0, k1[1]=v[s];
v1[0]=0, v1[1]=0;
n1[0]=0, n1[1]=1;
for(ll i=1;i<a1.size();i++){
for(ll j=b;j<=f;j++){
if(dp1[i][j]>k1[j]){
v1[j]=i;
if(nd1[i][j]){
n1[j]=1;
}
}
k1[j]=max(k1[j],dp1[i][j]);
}
b=b+1;
f=f+2;
}
vector<vector<ll>>dp2(a2.size(),vector<ll>(l,-1));
vector<vector<bool>>nd2(a2.size(),vector<bool>(l,0));
dp2[0][0]=0;
dp2[0][1]=v[s];
nd2[0][0]=0;
nd2[0][1]=1;
b=0,f=1;
for(ll i=1;i<a2.size();i++){
for(ll j=b;j<=f;j++){
if(dp2[i-1][j]+a2[i]>dp2[i][j+2]){
nd2[i][j+2]=nd2[i-1][j];
}
if(dp2[i-1][j]>dp2[i][j+1]){
nd2[i][j+1]=nd2[i-1][j];
}
dp2[i][j+2]=max(dp2[i][j+2], dp2[i-1][j]+a2[i]);
dp2[i][j+1]=max(dp2[i][j+1], dp2[i-1][j]);
}
b=b+1;
f=f+2;
}
vector<ll>k2(f+1,-1);
vector<ll>v2(f+1,-1);
vector<bool>n2(f+1,false);
b=1,f=3;
k2[0]=0, k2[1]=v[s];
v2[0]=0, v2[1]=0;
n2[0]=0, n2[1]=1;
for(ll i=1;i<a2.size();i++){
for(ll j=b;j<=f;j++){
if(dp2[i][j]>k2[j]){
v2[j]=i;
if(nd2[i][j]){
n2[j]=1;
}
}
k2[j]=max(k2[j],dp2[i][j]);
}
b=b+1;
f=f+2;
}
ll ans=0;
ll av,bv,vf;
for(ll i=0;i<k1.size();i++){
if(i>d) break;
for(ll j=0;j<k2.size();j++){
ll r=k1[i]+k2[j];
if(n1[i]&&n2[j]){
r-=v[s];
}
ll v=min(v1[i],v2[j]);
if(i+j+v<=d){
ans=max(ans,r);
}
}
}
return ans;
}
