#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn=1e5;
vector<array<ll,3> >isi;
vector<ll>ans;
ll n,dsu[maxn+2],mn[maxn+2][2],mn2[maxn+2][2],sum[maxn+2],sz[maxn+2];
ll fin(int a){
if(dsu[a]==a)return a;
return dsu[a]=fin(dsu[a]);
}
ll comp(int a){
a=fin(a);
if(sz[a]%2==0)return sum[a];
return sum[a]+min(mn2[a][a%2],mn[a][a%2]);
}
ll tot;
void merg(int a,int b){
if(b-a==2){
tot-=comp(fin(a));
int apa=fin(a);
mn2[apa][a%2]=min(mn2[apa][a%2],isi[a+1][1]-isi[a+1][2]);
// if(a==1){
// cout<<apa<<" "<<mn[apa][a%2]<<endl;
// }
tot+=comp(apa);
return;
}
a=fin(a),b=fin(b);
if(a==b)return;
tot-=comp(a)+comp(b);
if(a<b)swap(a,b);
dsu[a]=b;
sz[b]+=sz[a];
sum[b]+=sum[a];
mn[b][0]=min(mn[a][0],mn[b][0]);
mn[b][1]=min(mn[a][1],mn[b][1]);
mn2[b][0]=min(mn2[a][0],mn2[b][0]);
mn2[b][1]=min(mn2[a][1],mn2[b][1]);
tot+=comp(b);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
n=W.size();
for(int q=0;q<n;q++){
isi.pb({W[q],A[q],B[q]});
}
sort(isi.begin(),isi.end());
vector<pair<ll,ll> >inter,lain;
for(int q=0;q<n;q++){
dsu[q]=q,mn[q][0]=mn[q][1]=mn2[q][0]=mn2[q][1]=1e18;
mn[q][q%2]=isi[q][1]-isi[q][2];
sum[q]=isi[q][2]; sz[q]=1;
tot+=A[q];
if(q){
inter.pb({isi[q][0]-isi[q-1][0],q-1});
}
if(q>=2){
lain.pb({isi[q][0]-isi[q-2][0],q-2});
}
}
sort(inter.rbegin(),inter.rend());
sort(lain.rbegin(),lain.rend());
vector<pair<ll,ll> >qu;
for(int q=0;q<E.size();q++){
qu.pb({E[q],q});
ans.pb(0);
}
sort(qu.begin(),qu.end());
for(auto [mx,id] : qu){
while(inter.size() && (inter.back()).first<=mx){
auto [_,hah]=inter.back(); inter.pop_back();
merg(hah,hah+1);
}
//cout<<id<<" "<<fin(1)<<endl;
while(lain.size() && (lain.back()).first<=mx){
auto [_,hah]=lain.back(); lain.pop_back();
merg(hah,hah+2);
// if(hah==1){
// cout<<_<<" k "<<mn2[1][1]<<endl;
// }
}
ans[id]=tot;
}
return ans;
}
