#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
const ll INF = (ll)1e18;
const int MAXN = 100000;
int n, q;
ll baseB, extraCost;
struct Artifact { ll a, b, w; };
struct Edge { int u, v; ll cost; };
vector<Artifact> artifacts;
vector<Edge> edges; // holds both (i,i+1) and (i,i+2)
vector<int> parent, sz, minIdx;
vector<ll> minPar, minImpar, minBr;
int findRoot(int u) {
return parent[u] == u ? u : parent[u] = findRoot(parent[u]);
}
ll compCost(int r) {
if (sz[r] % 2 == 0) return 0;
ll byParity = (minIdx[r] % 2 == 0 ? minPar[r] : minImpar[r]);
return min(byParity, minBr[r]);
}
void unify(int u, int v) {
int ru = findRoot(u), rv = findRoot(v);
if (ru == rv) return;
extraCost -= compCost(ru) + compCost(rv);
if (sz[ru] > sz[rv]) swap(ru, rv);
parent[ru] = rv;
sz[rv] += sz[ru];
minIdx[rv] = min(minIdx[rv], minIdx[ru]);
minPar[rv] = min(minPar[rv], minPar[ru]);
minImpar[rv] = min(minImpar[rv], minImpar[ru]);
minBr[rv] = min(minBr[rv], minBr[ru]);
extraCost += compCost(rv);
}
void applyBrincable(int mid) {
int r = findRoot(mid);
extraCost -= compCost(r);
ll d = artifacts[mid].a - artifacts[mid].b;
minBr[r] = min(minBr[r], d);
extraCost += compCost(r);
}
vector<ll> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E
) {
n = W.size(); q = E.size();
artifacts.resize(n);
baseB = 0;
for (int i = 0; i < n; i++) {
artifacts[i] = { (ll)A[i], (ll)B[i], (ll)W[i] };
baseB += B[i];
}
// sort artifacts by weight
sort(artifacts.begin(), artifacts.end(),
[](auto &x, auto &y){ return x.w < y.w; });
// build edges for (i, i+1) and (i, i+2)
edges.clear();
for (int i = 0; i + 1 < n; i++)
edges.push_back({ i, i+1,
abs(artifacts[i+1].w - artifacts[i].w) });
for (int i = 0; i + 2 < n; i++)
edges.push_back({ i, i+2,
abs(artifacts[i+2].w - artifacts[i].w) });
sort(edges.begin(), edges.end(),
[](auto &x, auto &y){ return x.cost < y.cost; });
// init DSU arrays
parent.resize(n); sz.resize(n);
minIdx.resize(n);
minPar.assign(n, INF);
minImpar.assign(n, INF);
minBr.assign(n, INF);
extraCost = 0;
for (int i = 0; i < n; i++) {
parent[i] = i;
sz[i] = 1;
minIdx[i] = i;
ll d = artifacts[i].a - artifacts[i].b;
if (i % 2 == 0) minPar[i] = d;
else minImpar[i] = d;
extraCost += d;
}
// prepare queries
vector<pair<int,int>> queries(q);
for (int i = 0; i < q; i++)
queries[i] = { E[i], i };
sort(queries.begin(), queries.end());
// two-pointer sweep
vector<ll> answer(q);
int ei = 0; // index in edges
for (auto &qr : queries) {
int D = qr.first, qi = qr.second;
while (ei < (int)edges.size() && edges[ei].cost <= D) {
auto &e = edges[ei++];
if (e.v == e.u + 1) {
// merge adjacent
unify(e.u, e.v);
} else {
// enable brincable at mid = u+1
applyBrincable(e.u+1);
}
}
answer[qi] = baseB + extraCost;
}
return answer;
}
