#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
//const int N = 100;
ll s[4 * N];
int c[4 * N];
void turnOn(int v, int tl, int tr, int i, int val) {
if (tl + 1 == tr) {
c[v] = 1;
s[v] = val;
return;
}
int m = (tl + tr) / 2;
if (i < m)
turnOn(2 * v + 1, tl, m, i, val);
else
turnOn(2 * v + 2, m, tr, i, val);
c[v] = c[2 * v + 1] + c[2 * v + 2], s[v] = s[2 * v + 1] + s[2 * v + 2];
}
void turnOff(int v, int tl, int tr, int i) {
if (tl + 1 == tr) {
c[v] = 0;
s[v] = 0;
return;
}
int m = (tl + tr) / 2;
if (i < m)
turnOff(2 * v + 1, tl, m, i);
else
turnOff(2 * v + 2, m, tr, i);
c[v] = c[2 * v + 1] + c[2 * v + 2], s[v] = s[2 * v + 1] + s[2 * v + 2];
}
ll sum(int v, int tl, int tr, int k) {
if (c[v] <= 0 || k <= 0)
return 0;
if (c[v] <= k)
return s[v];
int m = (tl + tr) / 2;
return sum(2 * v + 1, tl, m, k) + sum(2 * v + 2, m, tr, k - c[2 * v + 1]);
}
int f[N], pos[N];
void countAll(int l, int r, int d_min, int d_max, int n, int a[]) {
if (l > r || d_min > d_max) return;
int d = (d_min + d_max) / 2;
ll s = 0;
f[d] = l;
for (int i = l; i <= r && d - i > 0; i++) {
turnOn(0, 0, n, pos[i], a[i]);
ll _sum = sum(0, 0, n, d - i);
if (_sum > s)
s = _sum, f[d] = i;
}
for (int i = l; i <= r && d - i > 0; i++)
turnOff(0, 0, n, pos[i]);
countAll(l, f[d], d_min, d-1, n, a);
countAll(f[d], r, d+1, d_max, n, a);
}
ll findMaxAttraction(int n, int start, int d, int a[]) {
assert(start == 0);
if (d == 0) return 0;
vector<pair<int, int> > t(n);
for(int i = 0; i < n; i++)
t[i] = {a[i], i};
sort(t.rbegin(), t.rend());
for (int i = 0; i < n; i++)
pos[t[i].second] = i;
countAll(0, n - 1, 0, d, n, a);
for (int i = 0; i <= f[d]; i++)
turnOn(0, 0, n, pos[i], a[i]);
ll ans = sum(0, 0, n, d - f[d]);
return ans;
}
