#include"holiday.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
#define ll long long
ll ans = 0;
int D,N;
vector<int> att;
void dfs(int pos,int len,ll cnt,set<int> visited){
if(len > D)return;
if(len == D){
// cerr << cnt << " | ";
// for(int a:visited)cerr << a;
// cerr << endl;
ans = max(ans,cnt);
return;
}
if(pos > 0){
dfs(pos-1,len+1,cnt,visited);
}
if(pos < N-1){
dfs(pos+1,len+1,cnt,visited);
}
if(visited.count(pos) == 0){
visited.insert(pos);
cnt += att[pos];
if(len+1 == D){
// cerr << cnt << " | ";
// for(int a:visited)cerr << a;
// cerr << endl;
ans = max(ans,cnt);
return;
}
if(pos > 0){
dfs(pos-1,len+2,cnt,visited);
}
if(pos < N-1){
dfs(pos+1,len+2,cnt,visited);
}
cnt -= att[pos];
visited.erase(pos);
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
D = d;
for(int i=0;i<n;i++)att.push_back(attraction[i]);
set<int> visited;
dfs(start,0,0,visited);
return ans;
}
