#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
namespace{
const ll mxN=1e5+5;
ll dsu[mxN], mn[mxN];
ll ans;
void add(ll tar){
ll siz=abs(dsu[tar]);
if(siz%2==1){
ans+=mn[tar];
}
}
void era(ll tar){
ll siz=abs(dsu[tar]);
if(siz%2==1){
ans-=mn[tar];
}
}
ll find_set(ll tar){
if(dsu[tar]<0) return tar;
return dsu[tar]=find_set(dsu[tar]);
}
void unite(ll a, ll b){
ll f=find_set(a);
ll s=find_set(b);
if(abs(dsu[f])<abs(dsu[s])) swap(f, s);
era(f);
era(s);
dsu[f]+=dsu[s];
mn[f]=min(mn[f], mn[s]);
dsu[s]=f;
add(f);
}
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
memset(dsu, -1, sizeof(dsu));
ll n=W.size();
ll q=E.size();
vll w(n), a(n), b(n);
vll ord(n);
for(ll i=0;i<n;i++){
ord[i]=i;
}
auto compare=[&](ll x, ll y){
return W[x]<W[y];
};
sort(ord.begin(), ord.end(), compare);
for(ll i=0;i<n;i++){
w[i]=W[ord[i]];
a[i]=A[ord[i]];
b[i]=B[ord[i]];
}
vector<array<ll, 2>> edges;
for(ll i=0;i<n;i++){
ans+=a[i];
mn[i]=a[i]-b[i];
if(i<n-1) edges.pb({w[i+1]-w[i], i});
}
vector<array<ll, 2>> qry;
for(ll i=0;i<q;i++){
qry.pb({E[i], i});
}
sort(qry.begin(), qry.end());
sort(edges.begin(), edges.end());
vll re(q);
ll pt=0;
for(auto &[x, y]:qry){
while(pt<(ll) edges.size() && edges[pt][0]<=x){
if(find_set(edges[pt][1])!=find_set(edges[pt][1]+1)){
unite(edges[pt][1], edges[pt][1]+1);
}
pt++;
}
re[y]=ans;
}
return re;
}
