#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 2;
int n, cnt[N], t[N * 4], sum[N * 4], ar[N];
void update(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
if(tl == tr){
t[v] += val;
sum[v] += val * ar[tl];
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm){
update(pos, val, v << 1, tl, tm);
} else {
update(pos, val, (v << 1) | 1, tm + 1, tr);
}
t[v] = t[v << 1] + t[(v << 1) | 1];
sum[v] = sum[v << 1] + sum[(v << 1) | 1];
}
}
pair <long long, int> get(int x, int v = 1, int tl = 1, int tr = N - 1){
if(!x || !sum[v]) return {0ll, 0};
if(t[v] <= x) return {sum[v], t[v]};
int tm = (tl + tr) >> 1;
pair <long long, int> f = get(x, (v << 1) | 1, tm + 1, tr);
pair <long long, int> s = get(x - f.second, (v << 1), tl, tm);
return {f.first + s.first, s.second + f.second};
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
int fl = 1;
long long ans = 0;
for(int i = 0; i < n; i ++)
if(attraction[i] > 100) fl = 0;
if(!start && fl){
for(int i = 0; i < n; i ++){
cnt[attraction[i]] ++;
long long res = 0;
if(i < d){
int now = d - i;
for(int i = 100; i >= 0; i --){
if(now >= cnt[i]){
res += cnt[i] * i;
now -= cnt[i];
} else {
res += now * i;
now = 0;
}
}
}
ans = max(ans, res);
}
} else {
vector <int> v;
for(int i = 0; i < n; i ++)
v.push_back(attraction[i]);
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for(int i = 0; i < n; i ++){
attraction[i] = lower_bound(v.begin(), v.end(), attraction[i]) - v.begin() + 1;
}
for(int i = 1; i <= n; i ++)
ar[i] = v[i - 1];
for(int t = 4; t <= d; t ++){
long long res1 = 0, res2 = 0;
for(int i = start; i < n; i ++){
if((i - start) * 2 >= t) break;
update(attraction[i], 1);
res1 = max(res1, get(t - (i - start) * 2).first);
}
for(int i = start; i < n; i ++){
if((i - start) * 2 >= t) break;
update(attraction[i], -1);
}
for(int i = start - 1; i >= 0; i --){
if((start - i) >= (d - t)) break;
update(attraction[i], 1);
res2 = max(res2, get((d - t) - (start - i)).first);
}
for(int i = start - 1; i >= 0; i --){
if((start - i) >= (d - t)) break;
update(attraction[i], -1);
}
ans = max(ans, res1 + res2);
}
for(int t = 0; t <= d; t ++){
long long res1 = 0, res2 = 0;
for(int i = start; i < n; i ++){
if((i - start) >= t) break;
update(attraction[i], 1);
res1 = max(res1, get(t - (i - start)).first);
}
for(int i = start; i < n; i ++){
if((i - start) >= t) break;
update(attraction[i], -1);
}
for(int i = start - 1; i >= 0; i --){
if((start - i) * 2 >= (d - t)) break;
update(attraction[i], 1);
res2 = max(res2, get((d - t) - (start - i) * 2).first);
}
for(int i = start - 1; i >= 0; i --){
if((start - i) * 2 >= (d - t)) break;
update(attraction[i], -1);
}
ans = max(ans, res1 + res2);
}
}
return ans;
}
