#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
pair<int,pair<long long,long long>> a[maxn];
long long sum;
priority_queue<pair<int,int>> pq;
struct Seg{
Seg *par;
int sz,l;
long long val[2][2];
Seg(long long x,int idx){
sz=1;
par=this;
val[0][0]=x;
val[0][1]=1e18;
val[1][0]=1e18;
val[1][1]=1e18;
l=idx;
}
Seg *rep(){
if(par==this)return this;
return par=par->rep();
}
void join(Seg *seg2){
if(sz%2)sum-=min(val[0][0],val[1][1]);
if(seg2->sz%2)sum-=min(seg2->val[0][0],seg2->val[1][1]);
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
val[i][j]=min(val[i][j],seg2->val[i^(sz&1)][j]);
}
}
if(sz>1)pq.push({a[seg2->l-2].first-a[seg2->l].first,seg2->l-1});
if(seg2->sz>1)pq.push({a[seg2->l-1].first-a[seg2->l+1].first,seg2->l});
seg2->par=this;
sz+=seg2->sz;
if(sz%2)sum+=min(val[0][0],val[1][1]);
}
};
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();
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,i);
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]->rep()->join(seg[x+1]->rep());
}
while(!pq.empty()&&pq.top().first<=d){
int x=pq.top().second;
pq.pop();
auto s=seg[x]->rep();
if(s->sz%2)sum-=min(s->val[0][0],s->val[1][1]);
s->val[(s->l+x)%2][1]=min(s->val[(s->l+x)%2][1],a[x].second.first-a[x].second.second);
if(s->sz%2)sum+=min(s->val[0][0],s->val[1][1]);
}
ans[idx]=sum;
}
return ans;
}
