#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
const int BASE = 1 << 17;
pair<int, int> atrac[BASE];
long long dp[BASE];
long long dp2[BASE];
int globD;
long long res = 0;
struct Node{
long long sum;
int count;
};
Node TREE[BASE << 1];
void update(int v, int sum){
v+= BASE;
if(sum < 0)
TREE[v].count = 0;
else TREE[v].count = 1;
TREE[v].sum += sum;
v/=2;
while(v > 0){
int l = 2*v, r = 2*v + 1;
TREE[v].count = TREE[l].count + TREE[r].count;
TREE[v].sum = TREE[l].sum + TREE[r].sum;
v/=2;
}
}
long long find(int v, int a, int b, int val){
if(TREE[v].count == 0) return 0;
else if(TREE[v].count <= val)
return TREE[v].sum;
else{
int l = 2*v, r = 2*v + 1, mid = (a+b)/2;;
if(TREE[r].count >= val) return find(r, mid+1, b, val);
return TREE[r].sum + find(l, a, mid, val);
}
}
int l = 0, r = 0;
void mo(int a, int b){
while(r < b){
++r;
update(atrac[r].second, atrac[r].first);
}
while(r > b){
update(atrac[r].second, -atrac[r].first);
r--;
}
while(l < a){
update(atrac[l].second, -atrac[l].first);
l++;
}
while(l > a){
--l;
update(atrac[l].second, atrac[l].first);
}
}
void dpc(int l, int r, int optl, int optr, int start){
int mid = (l+r)/2;
if(mid < start || r <= l) return;
mo(optl, mid);
int opt = optl;
for(int i = optl; i <= min(mid, optr) && i <= start; i++){
int cost = (start - i) + (mid - i);
if(globD - cost > 0){
long long earn = find(1, 0, BASE-1, globD - cost);
if(dp[mid] <= earn){
dp[mid] = earn;
res = max(res, earn);
opt = i;
}
}
update(atrac[i].second, -atrac[i].first);
}
dpc(l, mid, optl, opt, start);
dpc(mid+1, r, opt, optr, start);
}
void dpc2(int l, int r, int optl, int optr, int start){
int mid = (l+r)/2;
if(mid > start || r <= l) return;
mo(mid, optr);
int opt = optr;
for(int i = optr; i >= max(mid, optl) && i >= start; i--){
int cost = (i - start) + (i - mid);
if(globD - cost > 0){
long long earn = find(1, 0, BASE-1, globD - cost);
if(dp2[mid] <= earn){
dp2[mid] = earn;
res = max(res, earn);
opt = i;
}
}
update(atrac[i].second, -atrac[i].first);
}
dpc2(l, mid, optl, opt, start);
dpc2(mid+1, r, opt, optr, start);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
/*int main(){
int n, start, d;
vector<int> attraction;
cin >> n >> start >> d;
for(int i = 0; i < n; i++){
int xd;
cin >> xd;
attraction.push_back(xd);
}
*/
vector<pair<int, int>> pos;
for(int i = 0; i < n; i++)
pos.push_back({attraction[i], i});
sort(pos.begin(), pos.end());
for(int id = 0; id < n; id++)
atrac[pos[id].second] = {pos[id].first, id};
globD = d;
dpc(start, n-1, 0, n-1, start);
dpc2(0, start, 0, n-1, start);
// << res << endl;
return res;
}
