#include <bits/stdc++.h>
#define MAXN 100007
using namespace std;
long long seg[4*MAXN][2];
int dsu[MAXN],rb[MAXN],n;
int root(int u){
while(dsu[u]!=u)
{
dsu[u]=dsu[dsu[u]];
u=dsu[u];
}
return u;
}
void connect(int u,int v){
u=root(u);
v=root(v);
dsu[v]=u;
rb[u]=rb[v];
}
void build(int l,int r,int k,int ind){
seg[ind][k]=1000000000000000000LL;
if(l==r) return;
int s=(l+r)/2;
build(l,s,k,2*ind); build(s+1,r,k,2*ind+1);
}
void upd(int l,int r,int k, int g,int v,int ind)
{
if(l==r){
seg[ind][k]=v;
return;
}
int s=(l+r)/2;
if(g<=s) upd(l,s,k,g,v,2*ind);
else upd(s+1,r,k,g,v,2*ind+1);
seg[ind][k]=min(seg[2*ind][k],seg[2*ind+1][k]);
}
long long nmin(int l,int r,int k,int lt,int rt,int ind){
if(l>=lt && r<=rt) return seg[ind][k];
if(l>rt || r<lt) return 1000000000000000000LL;
int s=(l+r)/2;
return min(nmin(l,s,k,lt,rt,2*ind),nmin(s+1,r,k,lt,rt,2*ind+1));
}
long long skor(int l,int r){
if((r-l+1)&1) return nmin(0,n,l&1,l,r,1);
return 0;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
vector<long long> ans;
n=W.size();
long long rez=0;
for(int i=0;i<n;i++) rez+=A[i];
vector<pair<int,int>> v;
vector<pair<pair<int,int>,int>> events;
for(int i=0;i<n;i++) v.push_back({W[i],A[i]-B[i]});
sort(v.begin(),v.end());
for(int i=0;i<E.size();i++) {
events.push_back({{E[i],3},i});
ans.push_back(0);
}
for(int i=0;i+1<n;i++) events.push_back({{v[i+1].first-v[i].first,1},i});
for(int i=1;i+1<n;i++) events.push_back({{v[i+1].first-v[i-1].first,2},i});
sort(events.begin(),events.end());
for(int i=0;i<n;i++) dsu[i]=rb[i]=i;
build(0,n,0,1);
build(0,n,1,1);
for(int i=0;i<n;i++) upd(0,n,i&1,i,v[i].second,1);
for(int i=0;i<events.size();i++){
if(events[i].first.second==1){
int x=events[i].second;
rez-=skor(root(x),x);
rez-=skor(x+1,rb[x+1]);
connect(x,x+1);
rez+=skor(root(x),rb[x+1]);
}
if(events[i].first.second==2){
int x=events[i].second;
int l=root(x);
int r=rb[l];
rez-=skor(l,r);
upd(0,n,(x+1)&1,x,v[x].second,1);
rez+=skor(l,r);
}
if(events[i].first.second==3){
ans[events[i].second]=rez;
}
}
return ans;
}
