#include "holiday.h"
#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxn 100000
#define maxf 100
using namespace std;
int n;
int v[maxn+5], fv[maxf+5];
lll ans;
void umax (lll &a, lll b) { a = max(a,b); }
void dfs (int nod, int d, int mask, lll cur) {
if (nod < 0 || nod >= n || d <= 0) return;
dfs (nod-1, d-1, mask, cur);
dfs (nod+1, d-1, mask, cur);
if ((mask & (1<<nod)) == 0) {
cur += v[nod];
mask += (1<<nod);
umax(ans, cur);
dfs (nod, d-1, mask, cur);
}
}
lll biggest (int rem) {
int nr; lll cur = 0;
for (nr = maxf; nr > 0 && rem > 0; nr--)
if (rem > fv[nr]) {
cur += 1LL * fv[nr] * nr;
rem -= fv[nr];
} else {
cur += 1LL * rem * nr;
rem = 0;
}
return cur;
}
lll findMaxAttraction (int n_, int start_, int d_, int* v_) {
n = n_;
int start = start_, d = d_;
int i, j, z;
for (i = 0; i < n; i++) v[i] = v_[i];
if (n <= 20) {
dfs (start, d, 0, 0);
} else if (start == 0) {
for (j = 0; j < n; j++) {
fv[v[j]]++;
umax(ans, biggest(d-j));
}
}
return ans;
}
