#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
struct union_find {
int n;
vector<int> par, size, good;
vector<array<int, 2> > mn;
union_find(int _n) : n(_n), par(n+1), size(n+1, 1), good(n+1, 1e9), mn(n+1, { inf, inf }) {
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int u) {
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void uni(int a, int b) {
a = find(a); b = find(b);
if(a == b) return ;
size[a] += size[b];
par[b] = a;
good[a] = min(good[a], good[b]);
for(int i : { 0, 1 }) mn[a][i] = min(mn[a][i], mn[b][i]);
}
void set_mn(int p, int v) {
mn[p][p&1] = min(mn[p][p&1], v);
}
void set_good(int p, int v) {
good[find(p)] = min(good[find(p)], v);
}
int get_mn(int p) {
return mn[find(p)][find(p)%2];
}
int get_good(int u) {
return good[find(u)];
}
bool same_set(int a, int b) {
return find(a) == find(b);
}
int get_size(int u) {
return size[find(u)];
}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int q = E.size(), n = W.size();
vector<ll> ans(q);
vector<pair<int, int> > qus(q);
for(int i=0; i<q; i++) qus[i] = { E[i], i };
sort(qus.begin(), qus.end());
vector<array<int, 3> > edges, a(n+1);
for(int i=1; i<=n; i++) a[i] = { W[i-1], A[i-1], B[i-1] };
sort(a.begin()+1, a.end());
for(int i=1; i<n; i++) edges.push_back({ a[i+1][0] - a[i][0], i, i + 1 });
for(int i=1; i+2<=n; i++) edges.push_back({ a[i+2][0] - a[i][0], i, i + 2 });
sort(edges.begin(), edges.end());
union_find dsu(n);
ll res = 0;
for(int i=1; i<=n; i++) res += a[i][2];
for(int i=1; i<=n; i++) {
res += a[i][1] - a[i][2];
dsu.set_mn(i, a[i][1] - a[i][2]);
}
int p = 0;
for(auto [D, id] : qus) {
while(p < edges.size() && edges[p][0] <= D) {
if(edges[p][2] - edges[p][1] == 2) {
if(dsu.get_size(edges[p][1]) % 2 == 1)
res -= min(dsu.get_mn(edges[p][1]), dsu.get_good(edges[p][1]));
dsu.set_good(edges[p][1]+1, a[edges[p][1]+1][1] - a[edges[p][1]+1][2]);
if(dsu.get_size(edges[p][1]) % 2 == 1)
res += min(dsu.get_mn(edges[p][1]), dsu.get_good(edges[p][1]));
} else {
if(dsu.get_size(edges[p][1]) % 2 == 1)
res -= min(dsu.get_mn(edges[p][1]), dsu.get_good(edges[p][1]));
if(dsu.get_size(edges[p][2]) % 2 == 1)
res -= min(dsu.get_mn(edges[p][2]), dsu.get_good(edges[p][2]));
dsu.uni(edges[p][1], edges[p][2]);
if(dsu.get_size(edges[p][1]) % 2 == 1)
res += min(dsu.get_mn(edges[p][1]), dsu.get_good(edges[p][1]));
}
p++;
}
ans[id] = res;
}
return ans;
}
