#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
//template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector
#include "nile.h"
const ll inf=1e18;
struct DSU{
V<int> par,siz,L;
V<ll> mnc[2],mnspecial;
ll extra=0;
DSU(int n,const V<ll>& c){
par.rsz(n);
siz.ass(n,1);
L.rsz(n);
mnspecial.ass(n,inf);
mnc[0].ass(n,inf);
mnc[1].ass(n,inf);
iota(par.begin(),par.end(),0);
iota(L.begin(),L.end(),0);
FOR(i,n){
mnc[i%2][i]=c[i];
extra+=c[i];
}
}
int find(int i){
if(par[i]==i)return i;
return par[i]=find(par[i]);
}
ll get_comp_extra(int i){
if(!(siz[i]&1))return 0;
return min(mnc[L[i]%2][i],mnspecial[i]);
}
void merge(int i,int j){
i=find(i);
j=find(j);
if(i==j)return;
if(L[i]>L[j])swap(i,j);
extra-=get_comp_extra(i);
extra-=get_comp_extra(j);
par[j]=i;
siz[i]+=siz[j];
mnc[0][i]=min(mnc[0][i],mnc[0][j]);
mnc[1][i]=min(mnc[1][i],mnc[1][j]);
mnspecial[i]=min(mnspecial[i],mnspecial[j]);
extra+=get_comp_extra(i);
}
void activate(int i,ll val){
int r=find(i);
extra-=get_comp_extra(r);
mnspecial[r]=min(mnspecial[r],val);
extra+=get_comp_extra(r);
}
};
V<ll> calculate_costs(V<int> W,V<int> A,V<int> B,V<int> E){
int n=sz(W),q=sz(E);
V<int> p(n);
iota(p.begin(),p.end(),0);
sort(p.begin(),p.end(),[&](int i,int j){
return W[i]<W[j];
});
V<ll> c(n);
ll tot=0;
FOR(i,n){
c[i]=(ll)A[p[i]]-B[p[i]];
tot+=B[p[i]];
}
V<pii> events;
FOR(i,n-1){
events.pb({W[p[i+1]]-W[p[i]],(i<<1)});
if(i<n-2)events.pb({W[p[i+2]]-W[p[i]],(i<<1|1)});
}
sort(events.begin(),events.end());
V<int> ids(q);
FOR(i,q)ids[i]=i;
sort(ids.begin(),ids.end(),[&](int i,int j){
return E[i]<E[j];
});
DSU uf(n,c);
V<ll> res(q);
int ptr=0;
FOR(i,q){
int cur=ids[i],mxd=E[cur];
while(ptr<sz(events) && events[ptr].fi<=mxd){
int info=events[ptr].se,id=info>>1;
if(!(info&1))uf.merge(id,id+1);
else uf.activate(id+1,c[id+1]);
ptr++;
}
res[cur]=tot+uf.extra;
}
return res;
}
