#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;
const ll inf=1e18;
ll dsu[mxN], mn[mxN][3], lef[mxN], rig[mxN];
ll ans;
void add(ll tar){
ll siz=abs(dsu[tar]);
if(siz%2==1){
ans+=min(mn[tar][lef[tar]&1], mn[tar][2]);
}
}
void era(ll tar){
ll siz=abs(dsu[tar]);
if(siz%2==1){
ans-=min(mn[tar][lef[tar]&1], mn[tar][2]);
}
}
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][0]=min(mn[f][0], mn[s][0]);
mn[f][1]=min(mn[f][1], mn[s][1]);
mn[f][2]=min(mn[f][2], mn[s][2]);
lef[f]=min(lef[f], lef[s]);
rig[f]=max(rig[f], rig[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;
vector<array<ll, 2>> dumb;
ans=0;
for(ll i=0;i<n;i++){
ans+=a[i];
for(ll j=0;j<3;j++){
mn[i][j]=inf;
}
mn[i][i&1]=a[i]-b[i];
lef[i]=i;
rig[i]=i;
if(i<n-1) edges.pb({w[i+1]-w[i], i});
if(i>0 && i<n-1){
dumb.pb({w[i+1]-w[i-1], 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());
sort(dumb.begin(), dumb.end());
vll re(q);
ll pt=0, pt2=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++;
}
while(pt2<(ll) dumb.size() && dumb[pt2][0]<=x){
ll cur=dumb[pt2][1];
ll p=find_set(cur);
era(p);
mn[p][2]=min(mn[p][2], a[cur]-b[cur]);
add(p);
pt2++;
}
re[y]=ans;
}
return re;
}
