# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
# include "nile.h"
//# include "grader.cpp"
const long long INF=1e18;
const int MAX=1e5+11;
int n;
long long s;
pair<int,long long> a[MAX];
struct segtree
{
long long tree[MAX*4];
void build(int v=1, int l=0, int r=n)
{
if(l==r)
{
tree[v]=0;
return ;
}
int mid=(l+r)/2;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
tree[v]=max(tree[v*2],tree[v*2+1]);
}
void update(int pos, long long d, int v=1, int l=1, int r=n)
{
if(l==r)
{
tree[v]=max(tree[v],d);
return ;
}
int mid=(l+r)/2;
if(pos<=mid) update(pos,d,v*2,l,mid);
else update(pos,d,v*2+1,mid+1,r);
tree[v]=max(tree[v*2],tree[v*2+1]);
}
long long query(int le, int ri, int v=1, int l=1, int r=n)
{
if(ri<l or r<le) return 0;
if(le<=l and r<=ri) return tree[v];
int mid=(l+r)/2;
return max(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r));
}
}tree;
int lm[MAX];
long long dp[MAX];
long long calc(int d)
{
int ptr=1;
for(int i=1;i<=n;i++)
{
while(a[i].first-a[ptr].first>d) ptr++;
lm[i]=ptr;
}
tree.build();
for(int i=1;i<=n;i++) dp[i]=0;
for(int i=1;i<=n;i++)
{
if(lm[i]!=i) dp[i]=max(dp[i],tree.query(lm[i],i-1)+a[i].second);
dp[i]=max(dp[i],dp[i-1]);
tree.update(i,dp[i-1]+a[i].second);
}
long long ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
return ans;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
n=W.size();
for(int i=0;i<n;i++)
{
a[i+1]={W[i],A[i]-B[i]};
s+=A[i];
}
sort(a+1,a+n+1);
vector<pair<long long,long long>> ans;
long long from=1,res=calc(1);
ans.push_back({from,res});
while(from!=1e9+1)
{
int l=from,r=1e9,mx=l;
while(l<=r)
{
int mid=(l+r)/2;
long long resp=calc(mid);
if(resp==res)
{
l=mid+1;
mx=mid;
}
else r=mid-1;
}
if(mx==1e9) break;
from=mx+1;
res=calc(from);
ans.push_back({from,res});
}
//for(auto pa: ans) cout<<pa.first<<" "<<pa.second<<"\n";
vector<long long> Final;
Final.resize(E.size());
for(int i=0;i<(int)E.size();i++)
{
int id=upper_bound(ans.begin(),ans.end(),make_pair((long long)E[i],INF))-ans.begin()-1;
Final[i]=s-ans[id].second;
}
return Final;
}
/**
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5 9 1
*/
