#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
const int MAX = 1e5 + 5, oo = 1e9 + 7;
int n;
array<int, 2> arr[MAX];
ll ans = 0;
struct DSU{
int odd[MAX], even[MAX], mn[MAX];
int par[MAX];
void init(){
for(int i = 0; i < n; i++){
par[i] = -1;
odd[i] = arr[i][1];
even[i] = oo;
mn[i] = oo;
ans += arr[i][1];
}
}
int get(int a){
if(par[a] < 0) return a;
return par[a] = get(par[a]);
}
bool unite(int u, int v){
int i = v;
u = get(u), v = get(v);
if(u == v){
if((-par[u]) & 1) ans -= min(mn[u], odd[u]);
mn[u] = min(mn[u], arr[i][1]);
if((-par[u]) & 1) ans += min(mn[u], odd[u]);
return 0;
}
if((-par[u]) & 1) ans -= min(mn[u], odd[u]);
if((-par[v]) & 1) ans -= min(mn[v], odd[v]);
if((-par[u]) & 1){
odd[u] = min(odd[u], even[v]);
even[u] = min(even[u], odd[v]);
}
else{
odd[u] = min(odd[u], odd[v]);
even[u] = min(even[u], even[v]);
}
par[u] += par[v];
par[v] = u;
mn[u] = min(mn[u], mn[v]);
if((-par[u]) & 1) ans += min(mn[u], odd[u]);
return 1;
}
};
DSU dsu;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
n = W.size();
for(int i = 0; i < n; i++){
arr[i] = {W[i], A[i] - B[i]};
ans += B[i];
}
sort(arr, arr + n);
dsu.init();
vector<array<int, 3>> v;
for(int i = 0; i < n - 1; i++){
v.push_back({arr[i + 1][0] - arr[i][0], i, 1});
if(i < n - 2) v.push_back({arr[i + 2][0] - arr[i][0], i + 1, 0});
}
sort(all(v));
reverse(all(v));
vector<pii> Q;
for(int i = 0; i < E.size(); i++) Q.push_back({E[i], i});
sort(all(Q));
vector<ll> res(Q.size(), 0);
for(pii d : Q){
while(v.size() && v.back()[0] <= d.first){
if(v.back()[2]){
dsu.unite(v.back()[1], v.back()[1] + 1);
v.pop_back();
}
else{
dsu.unite(v.back()[1], v.back()[1]);
v.pop_back();
}
}
res[d.second] = ans;
}
return res;
}
