#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
#include<set>
#include "nile.h"
using namespace std;
const int MAX_N=1e5+5;
int parent[MAX_N];
int sz[MAX_N];
long long miodd[MAX_N];
long long mieven[MAX_N];
long long miadditional[MAX_N];
long long a[MAX_N];
long long b[MAX_N];
long long w[MAX_N];
int miid[MAX_N];
long long ans;
int n;
vector<pair<int,int>>order;
int Find(int u)
{
if(parent[u]==u)return u;
return parent[u]=Find(parent[u]);
}
long long calc(int u)
{
if(sz[u]%2==0)return 0;
long long res=a[miadditional[u]]-b[miadditional[u]];
if(miid[u]%2==0)
{
res=min(res,a[mieven[u]]-b[mieven[u]]);
}
else res=min(res,a[miodd[u]]-b[miodd[u]]);
return res;
}
void Merge(int u,int v)
{
int urt=Find(u);
int vrt=Find(v);
if(urt==vrt)
{
if(u+1==v)return;
int i=order[u+1].second;
long long additional=a[i]-b[i];
ans-=calc(urt);
if(additional<a[miadditional[urt]]-b[miadditional[urt]])
{
miadditional[urt]=i;
}
ans+=calc(urt);
return;
}
if(sz[urt]>sz[vrt])swap(urt,vrt);
ans-=calc(urt);ans-=calc(vrt);
sz[vrt]+=sz[urt];
parent[urt]=vrt;
if(a[miodd[urt]]-b[miodd[urt]]<a[miodd[vrt]]-b[miodd[vrt]])
{
miodd[vrt]=miodd[urt];
}
if(a[mieven[urt]]-b[mieven[urt]]<a[mieven[vrt]]-b[mieven[vrt]])
{
mieven[vrt]=mieven[urt];
}
if(miid[urt]<miid[vrt])
{
miid[vrt]=miid[urt];
}
if(a[miadditional[urt]]-b[miadditional[urt]]<a[miadditional[vrt]]-b[miadditional[vrt]])
{
miadditional[vrt]=miadditional[urt];
}
ans+=calc(vrt);
if(u+2==v)
{
int i=order[u+1].second;
long long additional=a[i]-b[i];
ans-=calc(vrt);
if(additional<a[miadditional[vrt]]-b[miadditional[vrt]])
{
miadditional[vrt]=i;
}
ans+=calc(vrt);
}
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
n=W.size();
ans=0;long long sumb=0;
for(int i=0;i<n;i++)
{
a[i]=A[i];
b[i]=B[i];
w[i]=W[i];
ans+=a[i]-b[i];
sumb+=b[i];
order.push_back({w[i],i});
}
sort(order.begin(),order.end());
vector<pair<long long,pair<int,int>>>gaps;
a[n]=(1LL<<60);
b[n]=0;
for(int i=0;i<n;i++)
{
int id=order[i].second;
parent[i]=i;
sz[i]=1;
miid[i]=i;
if(i%2==0)
{
mieven[i]=id;
miodd[i]=n;
}
else
{
miodd[i]=id;
mieven[i]=n;
}
miadditional[i]=n;
if(i+1<n)
{
gaps.push_back({order[i+1].first-order[i].first,{i,i+1}});
}
if(i+2<n)
{
gaps.push_back({order[i+2].first-order[i].first,{i,i+2}});
}
}
sort(gaps.begin(),gaps.end());
vector<pair<int,int>>queries;
for(int i=0;i<E.size();i++)
{
queries.push_back({E[i],i});
}
sort(queries.begin(),queries.end());
int idgap=0;
vector<long long>answers;
answers.resize((int)(queries.size()));
for(auto [d,id]:queries)
{
while(idgap<gaps.size() && gaps[idgap].first<=d)
{
int u,v;
tie(u,v)=gaps[idgap].second;
Merge(u,v);
idgap++;
}
answers[id]=ans+sumb;
}
return answers;
}
