#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int nmax=3e3+42;
vector<int> other;
int SZ;
priority_queue< pair<int/*value*/,int/*index*/> >pq,help;
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];
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)
{
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});
int rem=pq.size();
rem=min(d-(i-start),rem);
help=pq;
bool taken=0;
long long sum=0;
for(int j=0;j<=start;j++)
{
long long val=rec(d-2*(i-start)-j,taken);
ans=max(ans,sum+val);
//cout<<i<<" "<<j<<" -> "<<sum<<" "<<val<<endl;
if(help.size())
{
sum=sum-help.top().first;
if(help.top().second==start)taken=1;
help.pop();
}
}
}
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());
ans=max(ans,solve(n-1-start,d,now));
return ans;
}
/*
int att[5]={10,2,20,30,1};
int main()
{
cout<<findMaxAttraction(5,2,7,att)<<endl;
}
*/
