#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
ll cnt, sum;
node *l, *r;
node(): cnt(0), sum(0), l(0), r(0) {}
node(ll c, ll s): cnt(c), sum(s), l(0), r(0) {}
node(node* a, node* b): cnt(a->cnt+b->cnt), sum(a->sum+b->sum), l(a), r(b) {}
};
node *roots[100005];
int pospos[100005];
int D, ST;
node* build(int l, int r) {
//cout << l<<r<<'\n';
if(l ==r) return new node();
int mid = (l+r)/2;
return new node(build(l, mid), build(mid+1, r));
}
node *upd(node *old, int l, int r, int idx, ll val) {
if(l==r) return new node(1, val);
int mid = (l+r)/2;
if(idx <= mid) return new node(upd(old->l, l, mid, idx, val), old->r);
else return new node(old->l, upd(old->r, mid+1, r, idx, val));
}
ll qr(node *oldl, node *oldr, int k) {
if(oldr->cnt-oldl->cnt <= k) return oldr->sum-oldl->sum;
if(oldr->r->cnt-oldl->r->cnt >= k) return qr(oldl->r, oldr->r, k);
return qr(oldl->l, oldr->l, k-oldr->r->cnt+oldl->r->cnt) + oldr->r->sum - oldl->r->sum;
}
ll getmxbet(int l, int r, int cnt) {
if(cnt <= 0) return 0;
return qr(roots[l], roots[r+1], cnt);
}
ll cbans=0;
void rundp1(int l, int r, int posl, int posr) {
if(l>r) return;
int mid = (l+r) /2;
pair<ll, ll> bestans(0, mid);
for(int i=max(posl, mid); i<=posr; i++) {
//cout<<(mid) << ' ' << i << ' ' << ( D-ST-i+2*mid) << '\n';
bestans = max(bestans, {getmxbet(mid, i, D-ST-i+2*mid), i});
}
cbans = max(cbans, bestans.first);
rundp1(l, mid-1, posl, bestans.second);
rundp1(mid+1, r, bestans.second, posr);
}
void rundp2(int l, int r, int posl, int posr) {
if(l>r) return;
int mid = (l+r)/2;
pair<ll, ll> bestans(0, mid);
for(int i=posl; i<=min(mid, posr); i++) {
bestans = max(bestans, {getmxbet(i, mid, D-2*mid+ST+i), i});
}
cbans = max(cbans, bestans.first);
rundp2(l, mid-1, posl, bestans.second);
rundp2(mid+1, r, bestans.second, posr);
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
cbans=0;
D=d; ST=start;
roots[0] = build(0, n-1);
vector<pair<int, int>> idxval;
for(int i=0;i<n;i++) {
idxval.emplace_back(attraction[i], i);
}
sort(idxval.begin(), idxval.end());
for(int i=0;i<n;i++) {pospos[idxval[i].second]=i;}
for(int i=0;i<n;i++) {
roots[i+1] = upd(roots[i], 0, n-1, pospos[i], attraction[i]);
}
rundp1(0, start, 0, n-1);
rundp2(start, n-1, 0, n-1);
return cbans;
}
/*
int val[5] = {10, 2, 20, 30, 1};
int main() {
cout << findMaxAttraction(5, 2, 7, val);
//cout << qr(roots[2], roots[3], 5);
}*/
