#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int pos[N], p[N];
struct Node {
ll sum; int cnt;
Node(ll sum = 0, int cnt = 0) :
sum(sum), cnt(cnt) {}
} t[N << 2];
Node merge(Node a, Node b) {
return Node(a.sum + b.sum, a.cnt + b.cnt);
}
void update(int node, int l, int r, int i, int x) {
if(l == r) { t[node] = Node(x, 1); return; }
int m = l + r >> 1;
if(i <= m) update(node << 1, l, m, i, x);
else update(node << 1 | 1, m + 1, r, i, x);
t[node] = merge(t[node << 1], t[node << 1 | 1]);
}
ll query(int node, int l, int r, int k) {
if(l == r) return k ? t[node].sum : 0;
int m = l + r >> 1;
if(t[node << 1].cnt >= k) return query(node << 1, l, m, k);
else return query(node << 1 | 1, m + 1, r, k - t[node << 1].cnt) + t[node << 1].sum;
}
ll findMaxAttraction(int n, int start, int d, int a[]) {
iota(p, p + n, 0);
sort(p, p + n, [&](int i, int j) { return a[i] > a[j]; });
for(int i = 0; i < n; ++i) pos[p[i]] = i;
ll ans = 0;
for(int i = 0; i < n; ++i) {
if(i > d) break;
update(1, 1, n, pos[i], a[i]);
ans = max(ans, query(1, 1, n, d - i));
}
return ans;
}
