#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll INF = 1e18;
const int MAXN = 1e5;
struct DSU {
vector<ll> parent, size, sum, leftmost;
vector<ll> max_diff[2];
vector<ll> max_skip[2];
DSU(ll n) {
parent.resize(n);
size.resize(n, 1);
sum.resize(n);
leftmost.resize(n);
for (int i = 0; i < 2; i++) {
max_diff[i].resize(n, -INF);
max_skip[i].resize(n, -INF);
}
iota(parent.begin(), parent.end(), 0);
iota(leftmost.begin(), leftmost.end(), 0);
}
ll find(ll u) {
return parent[u] == u ? u : parent[u] = find(parent[u]);
}
void unite(ll u, ll v, ll val = -1) {
u = find(u);
v = find(v);
if (u == v) {
if (val != -1) {
ll parity = val % 2;
max_diff[parity][u] = max(max_diff[parity][u], Y[val] - X[val]);
}
return;
}
if (size[u] < size[v]) swap(u, v);
parent[v] = u;
size[u] += size[v];
sum[u] += sum[v];
leftmost[u] = min(leftmost[u], leftmost[v]);
for (int p = 0; p < 2; p++) {
max_diff[p][u] = max(max_diff[p][u], max_diff[p][v]);
max_skip[p][u] = max(max_skip[p][u], max_skip[p][v]);
}
if (val != -1) {
ll parity = val % 2;
max_diff[parity][u] = max(max_diff[parity][u], Y[val] - X[val]);
}
}
};
ll X[MAXN], Y[MAXN];
ll total_cost = 0;
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> result(Q);
vector<pii> artifacts;
for (int i = 0; i < N; i++) {
artifacts.emplace_back(W[i], i);
X[i] = A[i];
Y[i] = B[i];
}
sort(artifacts.begin(), artifacts.end());
vector<pair<pii, pii>> edges;
for (int i = 0; i < N; i++) {
if (i + 1 < N) edges.emplace_back(
pii{artifacts[i+1].first - artifacts[i].first, -1},
pii{artifacts[i].second, artifacts[i+1].second}
);
if (i + 2 < N) edges.emplace_back(
pii{artifacts[i+2].first - artifacts[i].first, artifacts[i+1].second},
pii{artifacts[i].second, artifacts[i+2].second}
);
}
sort(edges.begin(), edges.end());
vector<pii> queries;
for (int i = 0; i < Q; i++) queries.emplace_back(E[i], i);
sort(queries.begin(), queries.end());
DSU dsu(N);
total_cost = accumulate(A.begin(), A.end(), 0LL);
for (int i = 0; i < N; i++) {
int idx = artifacts[i].second;
dsu.sum[i] = B[idx] - A[idx];
dsu.max_skip[i % 2][i] = B[idx] - A[idx];
}
int edge_ptr = 0;
for (auto [d, q_idx] : queries) {
while (edge_ptr < edges.size() && edges[edge_ptr].first.first <= d) {
auto [val, mid] = edges[edge_ptr].first;
auto [u, v] = edges[edge_ptr].second;
dsu.unite(u, v, mid);
edge_ptr++;
}
result[q_idx] = total_cost;
}
return result;
}
