#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const ll INF = 4e18;
ll n, ans, cd, pa[N], sz[N], sm[N], op[N], ep[N], mn[N];
vector<tuple<int, ll, ll>> v;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int _find(int x){
if(x < 0 || x >= n) return -1;
if(x == pa[x]) return x;
return pa[x] = _find(pa[x]);
}
ll geta(int x){
x = _find(x);
if(sz[x] % 2 == 0) return sm[x];
else return sm[x] + min(op[x], mn[x]);
}
void _union(int x, int y){
ans -= geta(x), ans -= geta(y);
int X = _find(x), Y = _find(y);
if(sz[X] % 2 == 0){
sz[X] += sz[Y];
sm[X] += sm[Y];
op[X] = min(op[X], op[Y]);
ep[X] = min(ep[X], ep[Y]);
mn[X] = min(mn[X], mn[Y]);
pa[Y] = X;
}else{
sz[X] += sz[Y];
sm[X] += sm[Y];
op[X] = min(op[X], ep[Y]);
ep[X] = min(ep[X], op[Y]);
mn[X] = min(mn[X], mn[Y]);
pa[Y] = X;
}
if(x - 1 >= 0){
if(_find(x - 1) == _find(x) && get<0>(v[y]) - get<0>(v[x - 1]) <= cd) mn[X] = min(mn[X], get<1>(v[x]) - get<2>(v[x]));
else pq.push({get<0>(v[y]) - get<0>(v[x - 1]), x});
}
if(y + 1 < n){
if(_find(y) == _find(y + 1) && get<0>(v[y + 1]) - get<0>(v[x]) <= cd) mn[X] = min(mn[X], get<1>(v[y]) - get<2>(v[y]));
else pq.push({get<0>(v[y + 1]) - get<0>(v[x]), y});
}
pa[Y] = X;
ans += geta(X);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
n = W.size();
int Q = (int)E.size();
vector<ll> res(Q);
vector<pair<int, int>> df;
for(int i = 0;i<n;i++){
v.push_back({W[i], A[i], B[i]});
ans += A[i];
}
sort(v.begin(), v.end());
for(int i = 0;i<n - 1;i++){
df.push_back({get<0>(v[i + 1]) - get<0>(v[i]), i});
}
sort(df.begin(), df.end());
vector<pair<int, int>> qr;
for(int i = 0;i<Q;i++){
qr.push_back({E[i], i});
}
sort(qr.begin(), qr.end());
iota(pa, pa + n, 0);
for(int i = 0;i<n;i++) sm[i] = get<2>(v[i]), op[i] = get<1>(v[i]) - get<2>(v[i]), mn[i] = ep[i] = INF, sz[i] = 1;
int l = 0;
for(auto [x, id] : qr){
cd = x;
while(pq.size()){
auto [d, i] = pq.top();
if(d <= cd){
mn[_find(i)] = min(mn[_find(i)], get<1>(v[i]) - get<2>(v[i]));
pq.pop();
}else{
break;
}
}
while(l < n - 1 && df[l].first <= x){
_union(df[l].second, df[l].second + 1);
++l;
}
res[id] = ans;
}
return res;
}
