#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
ll n,par[maxn],no[maxn],sumofB[maxn],mnO[maxn],mnE[maxn],exO[maxn],exE[maxn];
ll ans=0;
set<pair<ll,ll>>vals;
array<ll,3>arr[maxn];
ll sol(vector<array<ll,3>>arr,ll d){
ll ans=1e18,sum=0,n=arr.size();
for(auto i:arr) sum+=i[2];
if(n%2==0) return sum;
for(int i=1;i<=arr.size();i++) if(i%2||arr[i+1][0]-arr[i-1][0]<=d) ans=min(ans,sum+arr[i][1]-arr[i][2]);
return ans;
}
ll dsu(ll x){
if(x==par[x]) return x;
return par[x]=dsu(par[x]);
}
void merge(ll a,ll b){
ll x=dsu(a),y=dsu(b);
ans-=sumofB[x];
if(no[x]%2) ans-=min(mnO[x],exE[x]);
ans-=sumofB[y];
if(no[y]%2) ans-=min(mnO[y],exE[y]);
if(no[x]%2==0){
mnO[x]=min(mnO[x],mnO[y]);
mnE[x]=min(mnE[x],mnE[y]);
exO[x]=min(exO[x],exO[y]);
exE[x]=min(exE[x],exE[y]);
}
else{
mnO[x]=min(mnO[x],mnE[y]);
mnE[x]=min(mnE[x],mnO[y]);
exO[x]=min(exO[x],exE[y]);
exE[x]=min(exE[x],exO[y]);
}
if(no[x]>1) vals.insert({arr[a+1][0]-arr[a-1][0],a});
if(no[y]>1) vals.insert({arr[b+1][0]-arr[b-1][0],b});
no[x]+=no[y];
sumofB[x]+=sumofB[y];
par[y]=x;
ans+=sumofB[x];
if(no[x]%2) ans+=min(mnO[x],exE[x]);
}
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();
vector<ll>anss(E.size());
for(int i=0;i<n;i++) arr[i]={W[i],A[i],B[i]};
sort(arr,arr+n);
set<pair<ll,ll>>diff;
for(int i=0;i<n;i++){
if(i) diff.insert({arr[i][0]-arr[i-1][0],i});
par[i]=i,no[i]=1,sumofB[i]+=arr[i][2],ans+=arr[i][1];
mnO[i]=arr[i][1]-arr[i][2],mnE[i]=exO[i]=exE[i]=1e18;
}
vector<pair<ll,ll>>ds;
for(int i=0;i<E.size();i++) ds.push_back({E[i],i});
sort(ds.begin(),ds.end());
for(auto [d,idd]:ds){
while(diff.size()&&diff.begin()->first<=d){
ll x=diff.begin()->second;
diff.erase(diff.begin());
merge(x,x-1);
}
while(vals.size()&&vals.begin()->first<=d){
auto[val,x]=*vals.begin();
vals.erase(vals.begin());
ll pa=dsu(x);
ans-=sumofB[pa];
if(no[pa]%2) ans-=min(mnO[pa],exE[pa]);
//
if((pa-x)%2) exE[pa]=min(exE[pa],arr[x][1]-arr[x][2]);
else exO[pa]=min(exO[pa],arr[x][1]-arr[x][2]);
//
ans+=sumofB[pa];
if(no[pa]%2) ans+=min(mnO[pa],exE[pa]);
}
anss[idd]=ans;
// cout<<d<<' '<<ans<<'\n';
}
return anss;
}
// int main(){
// calculate_costs({15, 12, 2, 10, 21},
// {5, 4, 5, 6, 3},
// {1, 2, 2, 3, 2},
// {5, 9, 1});
// }
