#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back
struct Seg{
int sz;
vector<vector<ll>> val;
};
const int maxn=1e5;
int par[maxn];
int rep(int x){
if(x==par[x])return x;
return par[x]=rep(par[x]);
}
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();
vector<ll> ans(q);
ll sum=0;
for(ll i:B)sum+=i;
pair<int,ll> a[n];
for(int i=0;i<n;i++){
a[i]={w[i],A[i]-B[i]};
}
sort(a,a+n);
Seg seg[n];
for(int i=0;i<n;i++){
seg[i].sz=1;
ll inf=1e18;
seg[i].val={{a[i].sc,inf},{inf,inf}};
sum+=a[i].sc;
par[i]=i;
}
pii df[n-1];
for(int i=0;i<n-1;i++){
df[i]={a[i+1].fs-a[i].fs,i};
}
sort(df,df+n-1);
pii qr[q];
for(int i=0;i<q;i++){
qr[i]={e[i],i};
}
sort(qr,qr+q);
priority_queue<pii> pq;
int idx=0;
for(int t=0;t<q;t++){
int x=qr[t].fs;
while(idx<n-1&&df[idx].fs<=x){
int c=df[idx].sc;
int r1=rep(c),r2=rep(c+1);
if(seg[r1].sz%2)sum-=min(seg[r1].val[0][0],seg[r1].val[1][1]);
if(seg[r2].sz%2)sum-=min(seg[r2].val[0][0],seg[r2].val[1][1]);
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
seg[r1].val[i][j]=min(seg[r1].val[i][j],seg[r2].val[i^(seg[r1].sz%2)][j]);
}
}
if(seg[r1].sz>1){
pq.push({a[c-1].fs-a[c+1].fs,c});
}
if(seg[r2].sz>1){
pq.push({a[c].fs-a[c+2].fs,c+1});
}
seg[r1].sz+=seg[r2].sz;
if(seg[r1].sz%2){
sum+=min(seg[r1].val[0][0],seg[r1].val[1][1]);
}
par[r2]=r1;
idx++;
}
while(!pq.empty()&&-pq.top().fs<=x){
int c=pq.top().sc;
pq.pop();
int r=rep(c),b=(c-r)%2;
if(seg[r].sz%2)sum-=min(seg[r].val[0][0],seg[r].val[1][1]);
seg[r].val[b][1]=min(seg[r].val[b][1],a[c].sc);
if(seg[r].sz%2)sum+=min(seg[r].val[0][0],seg[r].val[1][1]);
}
ans[qr[t].sc]=sum;
}
return ans;
}
