#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int nmax=7.5e3+42;
vector<int> other;
int SZ;
priority_queue< pair<int/*value*/,int/*index*/> >pq,help,emp;
priority_queue<int> idle;
long long mem[nmax][2];
long long rec(int d,bool taken)
{
//d=d-taken;
if(d<=0)return 0;
if(mem[d][taken]!=-1)return mem[d][taken];
priority_queue<int> q=idle;
long long ans=0,sum=0;
for(int i=taken;i<SZ;i++)
{
q.push(-other[i]);
sum=sum+other[i];
if(d-i<0)break;
while(q.size()>d-i)
{
sum=sum+q.top();
q.pop();
}
ans=max(ans,sum);
}
//for(auto k:other)cout<<k<<" ";cout<<" -> "<<d<<" "<<taken<<" "<<ans<<endl;
mem[d][taken]=ans;
return ans;
}
long long solve(int start,int d,vector<int> now)
{
/*
cout<<endl<<endl<<endl;
cout<<"now: ";for(auto k:now)cout<<k<<" ";cout<<endl;
*/
pq=emp;
memset(mem,-1,sizeof(mem));
other={};
for(int i=0;i<=start;i++)
other.push_back(now[i]);
reverse(other.begin(),other.end());
SZ=other.size();
//move right
long long ans=0;
int n=now.size();
for(int i=start;i<n;i++)
{
pq.push({now[i],i});
help=pq;
bool taken=0;
long long sum=0;
for(int j=0;i-start+j<=d;j++)
{
long long val=rec(d-2*(i-start)-j,taken);
ans=max(ans,sum+val);
/*
cout<<i<<" "<<j<<" -> "<<sum<<" "<<val<<endl;
cout<<help.top().first<<" "<<help.top().second<<endl;
cout<<endl;
*/
if(help.size())
{
sum=sum+help.top().first;
if(help.top().second==start)taken=1;
help.pop();
}
else break;
}
}
return ans;
}
long long findMaxAttraction(int n, int start, int d,int attraction[])
{
vector<int> now={};
for(int i=0;i<n;i++)now.push_back(attraction[i]);
long long ans=solve(start,d,now);
reverse(now.begin(),now.end());
//cout<<endl;
ans=max(ans,solve(n-1-start,d,now));
return ans;
}
/*
int att[3]={7,3,10};
int main()
{
cout<<findMaxAttraction(3,1,5,att)<<endl;
}
*/
