#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
ll N, S, D, res;
ll ST[400005], cur[400005];
ll A[400005], P[400005], Pr[400005], Sf[400005];
ll X[400005], Y[400005];
pair<ll, ll> C[400005];
void update(ll v, ll l, ll r, ll p, ll val) {
if(l == r) {
ST[v] = val;
cur[v] = (val > 0);
return;
}
ll md = (l + r) / 2;
if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
ST[v] = ST[v * 2] + ST[v * 2 + 1];
cur[v] = cur[v * 2] + cur[v * 2 + 1];
}
long long query(ll v, ll l, ll r, ll p) {
if(cur[v] == p) return ST[v];
ll md = (l + r) / 2;
if(p <= cur[v * 2])
return query(v * 2, l, (l + r) / 2, p);
return query(v * 2, l, (l + r) / 2, cur[v * 2])
+ query(v * 2 + 1, (l + r) / 2 + 1, r, p - cur[v * 2]);
}
long long query0(ll v, ll l, ll r, ll p) {
if(cur[v] == p) return ST[v];
ll md = (l + r) / 2;
if(p <= cur[v * 2 + 1])
return query0(v * 2 + 1, (l + r) / 2 + 1, r, p);
return query0(v * 2, l, (l + r) / 2, p - cur[v * 2 + 1])
+ query0(v * 2 + 1, (l + r) / 2 + 1, r, cur[v * 2 + 1]);
}
void solve(ll i, ll j, ll lo, ll hi) {
if(i > j) return;
ll md = (i + j) / 2;
for(ll l = lo; l <= hi; l++) {
update(1, S, N - 1, P[l], A[l]);
if(md - l + S > 0) {
long long ans = query(1, S, N - 1, min(cur[1], md - l + S));
if(Pr[md] < ans) {
Pr[md] = ans; X[md] = l;
}
}
}
for(ll l = lo; l <= hi; l++)
update(1, S, N - 1, P[l], 0);
solve(i, md - 1, lo, X[md]);
solve(md + 1, j, X[md], hi);
for(ll l = lo; l <= hi; l++)
update(1, S, N - 1, P[l], A[l]);
}
void solve0(ll i, ll j, ll lo, ll hi) {
if(i > j) return;
ll md = (i + j) / 2;
for(ll l = hi; l >= lo; l--) {
update(1, 0, S - 1, P[l], A[l]);
if(md - S + 1 + l > 0) {
long long ans = query0(1, 0, S - 1, min(cur[1], md - S + 1 + l));
if(Sf[md] < ans) {
Sf[md] = ans; Y[md] = l;
}
}
}
for(ll l = lo; l <= hi; l++)
update(1, 0, S - 1, P[l], 0);
solve0(i, md - 1, lo, Y[md]);
solve0(md + 1, j, Y[md], hi);
for(ll l = lo; l <= hi; l++)
update(1, 0, S - 1, P[l], A[l]);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n, S = start, D = d;
for(ll l = 0; l < N; l++) {
A[l] = attraction[l];
C[l] = {A[l], l};
}
sort(C, C + start); sort(C + start, C + N);
reverse(C + start, C + N);
for(ll l = 0; l < N; l++)
P[C[l].second] = l;
for(ll l = 0; l <= D; l++)
X[l] = S, Y[l] = S - 1;
if(start < N) solve(1, D, start, N - 1);
for(ll l = 0; l <= 4 * N; l++) ST[l] = cur[l] = 0;
if(start > 0) solve0(1, D, 0, start - 1);
res = max(Pr[D], Sf[D - 1]);
for(ll l = 0; l <= D; l++) {
if(D - l - X[l] + S - 1 >= 0)
res = max(res, Pr[l] + Sf[D - l - X[l] + S - 1]);
if(D - l - S + Y[l] - 1 >= 0)
res = max(res, Sf[l] + Pr[D - l - S + Y[l] - 1]);
}
return res;
}
