#include"holiday.h"
#include <map>
#define LL long long
#define MAXN 100005
using namespace std;
class DS {
map <int,int> M;
public:
void nuke() {M.clear();}
void add(int v) {
M[v]++;
}
LL ask(int num) {
if (M.empty()) {return(0);}
if (num < 0) {return(-1LL<<60);}
LL res = 0;
auto pt = --M.end();
while (num) {
if ((*pt).second > num) {
res += ((LL) num) * ((LL) (*pt).first);
num = 0;
} else {
res += ((LL) (*pt).second) * ((LL) (*pt).first);
num -= (*pt).second;
}
if (pt == M.begin()) {break;}
else {--pt;}
}
return(res);
}
} KQ;
LL ans;
int A[MAXN], D, S, N;
void slv(int l, int r, int lo, int hi) {
//printf("%d %d %d %d\n",l,r,lo,hi);
if (l > r) {return;}
int p = (l + r) >> 1;
LL opt=-1, optval=-1LL<<60;
for (int i=S; i<=p; i++) {
KQ.add(A[i]);
}
for (int i=hi; i>=lo; i--) {
KQ.add(A[i]);
LL res = KQ.ask(D-S + 2*i - p);
if (res >= optval) {
opt = i;
optval = res;
ans = max(ans, res);
}
}
KQ.nuke();
slv(l, p-1, lo, opt);
slv(p+1,r, opt, hi);
}
void slvL() {
for (int i=S; i>=0; i--) { //one direction
KQ.add(A[i]);
ans = max(ans, KQ.ask(D-S+i));
}
KQ.nuke();
slv(S+1, N-1, 0, S-1);
}
LL findMaxAttraction(int n, int s, int d, int a[]) { //len, start, days, val
N = n, S = s, D = d;
for (int i=0; i<n; i++) {A[i] = a[i];}
slvL();
for (int i=0; i<=n/2; i++) {
swap(A[i], A[n-1-i]);
}
S = N - 1 - S;
/*for (int i=0; i<N; i++) {
printf("%d ",A[i]);
}
printf("\n%d\n",S);
printf(" Flip\n"); */
slvL();
return(ans);
}
