#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll bst[1000007];
multiset<ll>st[1000007];
multiset<pair<ll,ll>>st2[1000007];
vector<pair<ll,pair<ll,ll>>>bts;
ll moj[1000007],moj2[1000007],gen[1000007],odd[1000007],even[1000007];
ll pol(ll x,ll d){
if((moj2[x]-moj[x])%2)return bst[x];
return bst[x]+min(min(gen[x],even[x]),min(bts[moj[x]].ss.ff-bts[moj[x]].ss.ss,bts[moj2[x]].ss.ff-bts[moj2[x]].ss.ss));
}
ll fnd(ll x){
if(moj[x]==x)return x;
return moj[x]=fnd(moj[x]);
}
vector<ll>calculate_costs(vector<int>w,vector<int>a,vector<int>b,vector<int>e){
multiset<pair<ll,ll>>s;
ll n=w.size();
vector<pair<ll,ll>>q;
for(ll i=0;i<e.size();i++){
q.pb({e[i],i});
}
bts.clear();
for(ll i=0;i<w.size();i++){
bts.pb({w[i],{a[i],b[i]}});
}
sort(bts.begin(),bts.end());
vector<pair<ll,ll>>zm;
for(ll i=0;i<w.size()-1;i++){
q.pb({bts[i+1].ff-bts[i].ff,-i-INFL});
if(i)
q.pb({bts[i+1].ff-bts[i-1].ff,-i-1});
}
sort(q.begin(),q.end());
ll akm=0;
for(ll i=0;i<n+7;i++){moj[i]=i;moj2[i]=i;}
for(ll i=0;i<w.size();i++){
even[i]=bts[i].ss.ff-bts[i].ss.ss;
odd[i]=INFL;
gen[i]=INFL;
bst[i]=bts[i].ss.ss;
akm+=bts[i].ss.ff;
}
vector<ll>ret;
vector<pair<ll,ll>>pm;
for(pair<ll,ll>i : q){
if(i.ss>=0){
pm.pb({i.ss,akm});
}
else if(i.ss>-INFL){
ll a=-i.ss-1;
ll pm=fnd(a);
akm-=pol(pm,i.ff);
gen[pm]=min(gen[pm],bts[a].ss.ff-bts[a].ss.ss);
akm+=pol(pm,i.ff);
}
else{
ll a=-i.ss-INFL;
ll p1=moj[a];
ll p2=moj[a+1];
akm-=pol(p1,i.ff);
akm-=pol(p2,i.ff);
if((moj2[p1]-p1)%2){
odd[p1]=min(odd[p1],odd[p2]);
even[p1]=min(even[p1],even[p2]);
}
else{
odd[p1]=min(odd[p1],even[p2]);
even[p1]=min(even[p1],odd[p2]);
}
gen[p1]=min(gen[p1],gen[p2]);
bst[p1]+=bst[p2];
moj[p2]=p1;
moj[moj2[p2]]=moj[p1];
moj2[moj[p1]]=moj2[p2];
akm+=pol(moj[p1],i.ff);
}
}
sort(pm.begin(),pm.end());
for(auto i : pm)ret.pb(i.ss);
return ret;
}
