#include "bits/stdc++.h"
#include "nile.h"
using namespace std;
struct DSU {
vector<int> parent;
DSU(int n) {
parent.assign(n, -1);
}
int find(int x) {
if (parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
bool same(int x, int y) {
return find(x) == find(y);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (parent[x] > parent[y]) swap(x, y);
parent[x] += parent[y];
parent[y] = x;
}
};
vector<long long> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E
) {
int N = W.size();
int Q = E.size();
vector<array<int, 3>> edges;
// Build valid edges: only pairs where weight difference ≤ 10
for (int w = 1; w <= 10; ++w) {
vector<int> ids;
for (int i = 0; i < N; ++i)
if (W[i] == w)
ids.push_back(i);
for (int d = 1; d <= 10; ++d) {
if (w + d > 10) break;
for (int u : ids) {
for (int v = 0; v < N; ++v) {
if (W[v] == w + d) {
edges.push_back({d, u, v});
}
}
}
}
}
sort(edges.begin(), edges.end()); // sort by weight diff
// Offline sort of queries
int q = E.size();
vector<int> ordQ(q);
iota(ordQ.begin(), ordQ.end(), 0);
sort(ordQ.begin(), ordQ.end(), [&](int i, int j) {
return E[i] < E[j];
});
vector<long long> res(q);
DSU dsu(N);
// Initial cost: send each artifact alone
long long total = 0;
for (int i = 0; i < N; ++i)
total += A[i];
int ei = 0;
for (int j = 0; j < q; ++j) {
int maxDiff = E[ordQ[j]];
// Add edges with weight difference ≤ D
while (ei < edges.size() && edges[ei][0] <= maxDiff) {
int u = edges[ei][1];
int v = edges[ei][2];
if (!dsu.same(u, v)) {
// Replace cost A[u] + A[v] with B[u] + B[v]
total -= (A[u] + A[v]);
total += (B[u] + B[v]);
dsu.unite(u, v);
}
++ei;
}
res[ordQ[j]] = total;
}
return res;
}
