#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define int long long
#define S second
#define F first
struct artifact{ll w,a,b,c;};
const int mxn=1e5+5;
vector<ll>p(mxn),sz(mxn),sum(mxn),cr(mxn),mno(mxn),mne(mxn),mn(mxn);
vector<artifact>v;
ll ret;
ll fp(ll i){
if(i==p[i])return i;
return p[i]=fp(p[i]);
}
void mrg(ll a,ll b){
bool flag=0;
// cout<<a<<' '<<b<<endl;
a=fp(a),b=fp(b);
if(sz[a]<sz[b])swap(a,b),flag=1;
if(flag==0){
if(sz[a]%2==0){
mno[a]=min(mno[a],mno[b]);
mne[a]=min(mne[a],mne[b]);
}
else{
mno[a]=min(mno[a],mne[b]);
mne[a]=min(mne[a],mno[b]);
}
}
else{
if(sz[b]%2==0){
mno[a]=min(mno[a],mno[b]);
mne[a]=min(mne[a],mne[b]);
}
else{
int x=mno[a];
mno[a]=min(mne[a],mno[b]);
mne[a]=min(x,mne[b]);
}
}
mn[a]=min(mn[a],mn[b]);
sum[a]+=sum[b];
sz[a]+=sz[b];
p[b]=a;
ret-=cr[a]+cr[b];
cr[a]=sum[a];
if(sz[a]%2)cr[a]+=min(mno[a],mn[a]);
ret+=cr[a];
// return;
// if(a==2&&b==1)return;
// cout<<"sz: "<<sz[a]<<endl;
// cout<<"sum: "<<sum[a]<<endl;
// cout<<"cr: "<<cr[a]<<endl;
// cout<<"mno: "<<mno[a]<<endl;
// cout<<"mne: "<<mne[a]<<endl;
// cout<<"mn: "<<mn[a]<<endl;
// cout<<endl<<endl;
}
vector<ll>calculate_costs(vector<signed>w,vector<signed>a,vector<signed>b,vector<signed>e){
int n=(int)w.size(),q=(int)e.size();
v.resize(n);
vector<ll>res(q);
set<pair<int,int>>s,t;
vector<pair<int,int>>qrys;
for(int i=0;i<q;i++)qrys.push_back({e[i],i});
for(int i=0;i<n;i++)v[i]={w[i],a[i],b[i],a[i]-b[i]};
sort(v.begin(),v.end(),[](auto a,auto b){return a.w<b.w;});
for(int i=0;i<n;i++){
p[i]=i;
sz[i]=1;
sum[i]=v[i].b;
cr[i]=v[i].a;
mno[i]=v[i].c;
mne[i]=1e18;
mn[i]=1e18;
cr[i]=v[i].a;
ret+=v[i].a;
}
for(int i=1;i<n;i++)s.insert({v[i].w-v[i-1].w,i});
for(int i=1;i<n-1;i++)t.insert({v[i+1].w-v[i-1].w,i});
sort(qrys.begin(),qrys.end());
for(int i=0;i<q;i++){
while(s.size()&&s.begin()->F<=qrys[i].F){
mrg(s.begin()->S-1,s.begin()->S);
s.erase(s.begin());
}
while(t.size()&&t.begin()->F<=qrys[i].F){
auto pr=fp(t.begin()->S);
mn[pr]=min(mn[pr],v[t.begin()->S].c);
ret-=cr[pr];
cr[pr]=sum[pr];
if(sz[pr]%2)cr[pr]+=min(mno[pr],mn[pr]);
ret+=cr[pr];
// cout<<"sz: "<<sz[pr]<<endl;
// cout<<"sum: "<<sum[pr]<<endl;
// cout<<"cr: "<<cr[pr]<<endl;
// cout<<"mno: "<<mno[pr]<<endl;
// cout<<"mne: "<<mne[pr]<<endl;
// cout<<"mn: "<<mn[pr]<<endl;
t.erase(t.begin());
}
res[qrys[i].S]=ret;
}
return res;
}
