#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
int n;
vector<int> p, sz, minIndex;
vector<ll> minC_par[2], minEnabled;
DSU(int _n=0): n(_n), p(n), sz(n), minIndex(n), minEnabled(n, (ll)9e18) {
for(int i=0; i<n; i++) {
p[i] = i;
sz[i] = 1;
minIndex[i] = i;
}
minC_par[0] = vector<ll>(n, (ll)9e18);
minC_par[1] = vector<ll>(n, (ll)9e18);
}
int find(int a) {
return p[a] == a ? a : p[a] = find(p[a]);
}
void unite_roots(int ra, int rb) {
if (ra == rb) return;
if (sz[ra] < sz[rb]) swap(ra, rb);
p[rb] = ra;
sz[ra] += sz[rb];
minIndex[ra] = min(minIndex[ra], minIndex[rb]);
for(int par = 0; par < 2; par++) {
minC_par[par][ra] = min(minC_par[par][ra], minC_par[par][rb]);
}
minEnabled[ra] = min(minEnabled[ra], minEnabled[rb]);
}
};
vector<ll> calculate_costs(
vector<int> W,
vector<int> A,
vector<int> B,
vector<int> E
) {
int N = W.size();
int Q = E.size();
vector<ll> w(N), a(N), b(N), e(Q);
for (int i = 0; i < N; i++) w[i] = W[i], a[i] = A[i], b[i] = B[i];
for (int i = 0; i < Q; i++) e[i] = E[i];
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j){
return w[i] < w[j] || (w[i] == w[j] && i < j);
});
vector<ll> sW(N), sA(N), sB(N);
for (int i = 0; i < N; i++) {
sW[i] = w[ord[i]];
sA[i] = a[ord[i]];
sB[i] = b[ord[i]];
}
vector<ll> C(N);
ll sumB = 0;
for (int i = 0; i < N; i++) {
C[i] = sA[i] - sB[i];
sumB += sB[i];
}
struct PairItem { ll diff; int i, j; int type; };
vector<PairItem> pairs;
for (int i = 0; i + 1 < N; i++) {
pairs.push_back({ sW[i+1] - sW[i], i, i+1, 1 });
}
for (int i = 0; i + 2 < N; i++) {
pairs.push_back({ sW[i+2] - sW[i], i, i+2, 2 });
}
sort(pairs.begin(), pairs.end(), [](const PairItem& A, const PairItem& B) {
if (A.diff != B.diff) return A.diff < B.diff;
return A.type < B.type;
});
vector<int> qidx(Q);
iota(qidx.begin(), qidx.end(), 0);
sort(qidx.begin(), qidx.end(), [&](int i, int j) {
if (e[i] != e[j]) return e[i] < e[j];
return i < j;
});
DSU dsu(N);
for (int i = 0; i < N; i++) {
dsu.minC_par[ i & 1 ][i] = C[i];
}
auto comp_contrib = [&](int root) {
if (dsu.sz[root] % 2 == 0) return 0LL;
int L = dsu.minIndex[root];
int par = L & 1;
ll best = min(dsu.minC_par[par][root], dsu.minEnabled[root]);
return best;
};
ll extra_sum = 0;
for (int i = 0; i < N; i++) extra_sum += C[i];
vector<char> enabled(N, 0);
int pptr = 0;
vector<ll> ans(Q);
for (int qi = 0; qi < Q; qi++) {
int qi0 = qidx[qi];
ll D = e[qi0];
while (pptr < (int)pairs.size() && pairs[pptr].diff <= D) {
auto &pr = pairs[pptr];
if (pr.type == 2) {
int mid = pr.i + 1;
if (!enabled[mid]) {
enabled[mid] = 1;
int r = dsu.find(mid);
extra_sum -= comp_contrib(r);
dsu.minEnabled[r] = min(dsu.minEnabled[r], C[mid]);
extra_sum += comp_contrib(r);
}
} else {
int u = pr.i, v = pr.j;
int ru = dsu.find(u), rv = dsu.find(v);
if (ru != rv) {
extra_sum -= comp_contrib(ru) + comp_contrib(rv);
dsu.unite_roots(ru, rv);
int r = dsu.find(ru);
extra_sum += comp_contrib(r);
}
}
pptr++;
}
ans[qi0] = sumB + extra_sum;
}
return ans;
}
