#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mxN = 30+5;
int d;
ll f(vector<int> a, int s) {
int n = a.size();
vector<ll> l(d+1, 0), r(d+1, 0);
if (s>0) {
l[1] = a[s-1];
for (int i=2; i<=d; i++) {
l[i] = l[i-1];
}
}
vector<ll> mx = l;
//cout << d << endl;
for (int i=s-2; i>=0; i--) {
//cout << i << endl;
vector<ll> nw(d+1, 0);
for (int j=(s-1)-i; j<=d; j++) {
nw[j] = l[j-1];
if (j>=2) {
nw[j] = max(nw[j], a[i]+l[j-2]);
}
}
l = nw;
for (int j=0; j<=d; j++) {
mx[j] = max(mx[j], l[j]);
}
}
r[1] = a[s];
for (int i=2; i<=d; i++) {
r[i] = r[i-1];
}
ll ans=0;
for (int j=0; j<=d; j++) {
ans = max(ans, r[j]+l[d-1]);
}
//cout << d << endl;
for (int i=s+1; i<n; i++) {
vector<ll> nw(d+1);
//cout << i << endl;
for (int j=i-s; j<=d; j++) {
nw[j] = r[j-1];
if (j>=2) {
nw[j] = max(nw[j], r[j-2]+a[i]);
}
}
for (int j=i-s; j<=d; j++) {
int dis = i-(s-1);//distancia a s-1;
int t = j+dis;
ans = max(ans, nw[j]);
//cout << nw[j] << " " << d-t << " " << (d-t>=0 ? mx[d-t] : 0) << endl;
if (s>0 && d-t>=0) {
ans = max(ans, nw[j]+mx[d-t]);
}
}
r = nw;
}
return ans;
}
int s;
ll findMaxAttraction(int n, int S, int D, int A[]) {
if (D==0) return 0;
s = S;
d = D;
vector<int> a(n);
for (int i=0; i<n; i++) {
a[i] = A[i];
}
ll ans = f(a, s);
reverse(a.begin(), a.end());
s = n-1-s;
ans = max(ans, f(a, s));
return ans;
}
