#include <bits/stdc++.h>
#include "holiday.h"
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
int s=0;
int n;
vector<vector<vector<vector<int>>>> memo;
vector<int> a;
int dp1(int x, int d, bool changedir){
if(d==0) return 0;
else if(d<0) return -1e9;
if(memo[x][d][changedir][0]>-1) return memo[x][d][changedir][0];
int mx=0;
int nxt=0;
int nxtCH=0;
int nxtCH2=0;
int nxt2=0;
if(!changedir){
if(x>0){
nxt=dp1(x-1,d-1,false);
nxt2=dp1(x-1,d-2,false);
}
if(x<n-1){
nxtCH=dp1(x+1,d-1,true);
nxtCH2=dp1(x+1,d-2,true);
}
}else{
if(x<n-1){
nxt=dp1(x+1,d-1,true);
nxt2=dp1(x+1,d-2,true);
}
}
mx=max(mx,nxt);
if(!changedir) mx=max(mx,nxtCH);
if(!changedir||x>s){
if(d==1){
mx=max(mx,a[x]);
}else{
mx=max(mx,a[x]+nxt2);
if(!changedir) mx=max(mx,a[x]+nxtCH2);
}
}
return memo[x][d][changedir][0]=mx;
}
int dp2(int x, int d, bool changedir){
if(d==0) return 0;
else if(d<0) return -1e9;
if(memo[x][d][changedir][1]>-1) return memo[x][d][changedir][1];
int mx=0;
int nxt=0;
int nxtCH=0;
int nxtCH2=0;
int nxt2=0;
if(!changedir){
if(x<n-1){
nxt=dp2(x+1,d-1,false);
nxt2=dp2(x+1,d-2,false);
}
if(x>0){
nxtCH=dp2(x-1,d-1,true);
nxtCH2=dp2(x-1,d-2,true);
}
}else{
if(x>0){
nxt=dp2(x-1,d-1,true);
nxt2=dp2(x-1,d-2,true);
}
}
mx=max(mx,nxt);
if(!changedir) mx=max(mx,nxtCH);
if(!changedir||x<s){
if(d==1){
mx=max(mx,a[x]);
}else{
mx=max(mx,a[x]+nxt2);
if(!changedir) mx=max(mx,a[x]+nxtCH2);
}
}
return memo[x][d][changedir][1]=mx;
}
int findMaxAttraction(signed N, signed start, signed d, signed attraction[]) {
s=start;
a.resize(N);
n=sz(a);
for (int i = 0; i < n; i++) a[i]=attraction[i];
memo.resize(n,vector<vector<vector<int>>>(d+1,vector<vector<int>>(2,vector<int>(2,-1))));
int sm=dp1(s,d,0);
sm=max(sm,dp2(s,d,0));
return sm;
}
