// Sample grader
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define pb push_back
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
long long dp[3000][7501];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= d; ++j)
{
dp[i][j]=-1e18;
}
}
dp[start][0]=0;
long long ans=0;
for (int i = start; i >= 0; --i)
{
for (int j = d; j >= 0; --j)
{
if(j){
dp[i][j]=max(dp[i][j-1]+1ll*attraction[i],dp[i][j]);
}
if(i&&j<d){
dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]);
}
if(start-i+j+1<=d&&start<n-1){
dp[start+1][j+start-i+1]=max(dp[i][j],dp[start+1][j+start-i+1]);
}
ans=max(ans,dp[i][j]);
}
}
for (int i = start+1; i < n; ++i)
{
for (int j = d; j >= 0; --j)
{
if(j){
dp[i][j]=max(dp[i][j],dp[i][j-1]+1ll*attraction[i]);
}
if(i<n-1&&j<d){
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
}
ans=max(ans,dp[i][j]);
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= d; ++j)
{
dp[i][j]=-1e18;
}
}
dp[start][0]=0;
ans=0;
for (int i = start; i < n; ++i)
{
for (int j = d; j >= 0; --j)
{
if(j){
dp[i][j]=max(dp[i][j-1]+1ll*attraction[i],dp[i][j]);
}
if(i<n-1&&j<d){
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
}
if(i-start+j+1<=d&&start>0){
//cout <<i<<" "<<j<<" "<<j-start+i+1<<" "<<dp[i][j]<<endl;
dp[start-1][j-start+i+1]=max(dp[i][j],dp[start-1][j-start+i+1]);
}
ans=max(ans,dp[i][j]);
}
}
for (int i = start-1; i >= 0; --i)
{
for (int j = d; j >= 0; --j)
{
if(j){
dp[i][j]=max(dp[i][j],dp[i][j-1]+attraction[i]);
}
if(i&&j<d){
dp[i-1][j+1]=max(dp[i-1][j+1],dp[i][j]);
}
ans=max(ans,dp[i][j]);
}
}
return ans;
}
