#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,inf=1e9;
ll ans;
int n,q,C[N];
int par[N],mn[N][3],sajz[N];
void Init(){
for(int i=0;i<n;i++){
par[i]=i;
mn[i][0]=C[i];
sajz[i]=1;
mn[i][1]=mn[i][2]=inf;
}
}
int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
void US(int u,int v){
u=FS(u),v=FS(v);
if(u==v) return;
par[v]=u;
int bit=sajz[u]&1;
mn[u][0]=min(mn[u][0],mn[v][bit]);
mn[u][1]=min(mn[u][1],mn[v][bit^1]);
mn[u][2]=min(mn[u][2],mn[v][2]);
sajz[u]+=sajz[v];
}
int MIN(int u){u=FS(u);if(sajz[u]&1) return min(mn[u][0],mn[u][2]);return 0;}
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(),q=E.size();
array<int,3>nesto[n+10];
for(int i=0;i<n;i++) nesto[i]={W[i],A[i],B[i]};
sort(nesto,nesto+n);
for(int i=0;i<n;i++) W[i]=nesto[i][0],A[i]=nesto[i][1],B[i]=nesto[i][2];
//for(int i=0;i<n;i++) printf("%i %i %i\n",W[i],A[i],B[i]);
for(int i=0;i<n;i++) C[i]=A[i]-B[i];
vector<array<int,3>>ev;
for(int i=0;i<n;i++){
if(i>=1) ev.pb({W[i]-W[i-1],i-1,i});
if(i>=2) ev.pb({W[i]-W[i-2],i-2,i});
}
sort(ev.begin(),ev.end());
//for(auto i:ev) printf("%i %i %i\n",i[0],i[1],i[2]);
vector<pair<int,int>>Qs;
vector<ll>res(q);
for(int i=0;i<q;i++)Qs.pb({E[i],i});
sort(Qs.begin(),Qs.end());
for(int i=0;i<n;i++) ans+=A[i];
Init();
for(int I=0,j=0;I<q;I++){
int d=Qs[I].fi;
while(j<ev.size()&&ev[j][0]<=d){
int u=ev[j][1],v=ev[j][2];
if(u+1==v){
ans-=MIN(u)+MIN(v);
US(u,v);
ans+=MIN(u);
}
else{
int x=u+1,rt=FS(x);
ans-=MIN(rt);
mn[rt][2]=min(mn[rt][2],C[x]);
ans+=MIN(rt);
}
//printf("%i: ",j);for(int i=0;i<n;i++) printf("%i ",MIN(i));printf("\n");
j++;
}
res[Qs[I].se]=ans;
}
return res;
}
