#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct DSU {
int n;
ll ans;
vector<int> parent, size, mins;
vector<ll> sum;
DSU(int n, vector<vector<int>> arr) : n(n), ans(0), parent(n), size(n, 1), mins(n),sum(n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
int a = arr[i][1], b = arr[i][2];
mins[i] = a - b;
ans += a;
sum[i] = b;
}
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
ll contrib(int x) {
return sum[x] + (size[x] % 2) * mins[x];
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
ans -= contrib(a) + contrib(b);
size[a] += size[b];
sum[a] += sum[b];
mins[a] = min(mins[a], mins[b]);
ans += contrib(a);
return true;
}
};
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<vector<int>> arr(n, vector<int>(3));
for (int i = 0; i < n; i++) {
arr[i][0] = W[i];
arr[i][1] = A[i];
arr[i][2] = B[i];
}
sort(arr.begin(), arr.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
auto comp = [](pii a, pii b) {
return a.second > b.second;
};
priority_queue<pii, vector<pii>, decltype(comp)> pq(comp);
for (int i = 0; i < n - 1; i++) {
pq.push({i, arr[i + 1][0] - arr[i][0]});
}
DSU dsu(n, arr);
vector<pii> queries(q);
for (int i = 0; i < q; i++) {
queries[i] = {i, E[i]};
}
sort(queries.begin(), queries.end(), [](const pii& a, const pii& b) {
return a.second < b.second;
});
vector<ll> ans(q);
for (int qi = 0; qi < q; qi++) {
auto [j, d] = queries[qi];
while (!pq.empty() && pq.top().second <= d) {
int i = pq.top().first;
pq.pop();
dsu.unite(i, i + 1);
}
ans[j] = dsu.ans;
}
return ans;
}
