#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pipii pair<int,pii>
#define f first
#define s second
const int maxn=1e5+5;
const int blk=0x3f3f3f3f3f3f3f3f;
pii queries[maxn],diff[maxn],diff2[maxn];
pipii u[maxn];
int par[maxn],siz[maxn],sum[maxn],res[maxn];
int odd[maxn],even[maxn],odd2[maxn],even2[maxn];
int n,q,top,top2,ans;
int fp(int x) {return par[x]==x?x:par[x]=fp(par[x]);}
void merge(int a,int b){
a=fp(a);b=fp(b);
ans-=res[a]+res[b];
if(siz[a]&1){
odd[a]=min(odd[a],even[b]);
even[a]=min(even[a],odd[b]);
odd2[a]=min(odd2[a],even2[b]);
even2[a]=min(even2[a],odd2[b]);
}else{
odd[a]=min(odd[a],odd[b]);
even[a]=min(even[a],even[b]);
odd2[a]=min(odd2[a],odd2[b]);
even2[a]=min(even2[a],even2[b]);
}
sum[a]+=sum[b];
siz[a]+=siz[b];
par[b]=a;
if(siz[a]&1) res[a]=sum[a]+min(odd[a],even2[a]);
else res[a]=sum[a];
//cout<<sum[a]<<' '<<odd[a]<<' '<<even[a]<<' '<<odd2[a]<<' '<<even2[a]<<'\n';
ans+=res[a];
}
void update(int x){
int a=fp(x);
if((x-a)&1) even2[a]=min(even2[a],u[x].s.f-u[x].s.s);
else odd2[a]=min(odd2[a],u[x].s.f-u[x].s.s);
ans-=res[a];
if(siz[a]&1) res[a]=sum[a]+min(odd[a],even2[a]);
else res[a]=sum[a];
ans+=res[a];
//cout<<sum[a]<<' '<<odd[a]<<' '<<even[a]<<' '<<odd2[a]<<' '<<even2[a]<<'\n';
}
vector<int> calculate_costs(vector<signed> W,vector<signed> A,vector<signed> B,vector<signed> E){
n=W.size(),q=E.size();
vector<int> out;
out.resize(q);
for(int i=0;i<q;i++) queries[i]={E[i],i};
sort(queries,queries+q);
for(int i=0;i<n;i++) u[i]={W[i],{A[i],B[i]}};
sort(u,u+n);
for(int i=0;i<n;i++){
par[i]=i;
siz[i]=1;
sum[i]=u[i].s.s;
odd[i]=u[i].s.f-u[i].s.s;
even[i]=odd2[i]=even2[i]=blk;
ans+=res[i]=u[i].s.f;
}
for(int i=0;i<n-1;i++) diff[i]={u[i+1].f-u[i].f,i};
sort(diff,diff+(n-1));
for(int i=0;i<n-2;i++) diff2[i]={u[i+2].f-u[i].f,i+1};
sort(diff2,diff2+(n-2));
//for(int i=0;i<n;i++) cout<<u[i].f<<' '; cout<<'\n';
//for(int i=0;i<n-1;i++) cout<<diff[i].f<<' '<<diff[i].s<<" "; cout<<'\n';
//for(int i=0;i<n-2;i++) cout<<diff2[i].f<<' '<<diff2[i].s<<" "; cout<<'\n';
for(int i=0;i<q;i++){
//cout<<queries[i].f<<" ------------\n";
while(top<n-1&&diff[top].f<=queries[i].f){
//cout<<"merge "<<diff[top].s<<' '<<diff[top].s+1<<'\n';
merge(diff[top].s,diff[top].s+1);
top++;
}
while(top2<n-2&&diff2[top2].f<=queries[i].f){
//cout<<"update "<<diff2[top2].f<<' '<<diff2[top2].s<<'\n';
update(diff2[top2].s);
top2++;
}
out[queries[i].s]=ans;
//cout<<ans<<'\n';
}
return out;
}
/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5 9 1
*/
