#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << ": " << x << '\n';
vector<ll> arr;
vector<vector<ll>> dp;
int n;
ll ans = 0;
ll s;
void derecha(int d, int curr, ll sum){
if(d <= 0 or curr >= n){
ans = max(ans, sum);
return;
}
derecha(d - 1, curr + 1, sum);
derecha(d - 2, curr + 1, sum + arr[curr]);
}
void izquierda(int d, int curr, ll sum){
if(d <= 0 or curr < 0){
ans = max(ans, sum);
return;
}
izquierda(d - 1, curr - 1, sum);
izquierda(d - 2, curr - 1, sum + arr[curr]);
}
void izqder(int d, int curr, ll sum){
if(d <= 0 or curr < 0){
ans = max(ans, sum);
return;
}
izqder(d - 1, curr - 1, sum);
izqder(d - 2, curr - 1, sum + arr[curr]);
derecha(d - abs(s - curr) - 1, s + 1, sum);
derecha(d - abs(s - curr) - 2, s + 1, sum + arr[curr]);
}
void derizq(int d, int curr, ll sum){
if(d <= 0 or curr >= n){
ans = max(ans, sum);
return;
}
derizq(d - 1, curr + 1, sum);
derizq(d - 2, curr + 1, sum + arr[curr]);
izquierda(d - abs(s - curr) - 1, s - 1, sum);
izquierda(d - abs(s - curr) - 2, s - 1, sum + arr[curr]);
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
s = start;
arr.assign(n, 0);
copy(attraction, attraction + n, arr.begin());
izqder(d, start, 0);
derizq(d, start, 0);
return ans;
}
