#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
long long sum;
struct Seg{
Seg *par;
long long sz,val;
Seg(long long x){
sz=1;
par=this;
val=x;
}
Seg *rep(){
if(par==this)return par;
return par=par->rep();
}
void join(Seg *seg2){
if(sz%2)sum-=val;
if(seg2->sz%2)sum-=seg2->val;
seg2->par=this;
sz+=seg2->sz;
if(sz%2)sum+=val;
}
};
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int n=W.size(),q=E.size();
pair<int,pair<long long,long long>> a[n+1];
for(int i=0;i<n;i++)a[i]={W[i],{A[i],B[i]}};
sort(a,a+n);
pair<int,int> qry[q],ds[n-1];
for(int i=0;i<q;i++)qry[i]={E[i],i};
sort(qry,qry+q);
for(int i=0;i<n-1;i++)ds[i]={a[i+1].first-a[i].first,i};
sort(ds,ds+n-1);
vector<long long> ans(q);
Seg *seg[n];
for(int i=0;i<n;i++){
seg[i]=new Seg(a[i].second.first-a[i].second.second);
sum+=a[i].second.first;
}
int ni=0;
for(auto[d,idx]:qry){
while(ni<n-1&&ds[ni].first<=d){
int x=ds[ni++].second;
seg[x]->par->join(seg[x+1]->par);
}
ans[idx]=sum;
}
return ans;
}
