#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 1e9;
struct DSU {
int n;
ll ans;
vector<int> parent, l, size, min1, min2, specialMin1, specialMin2;
vector<ll> sum;
DSU(int n, vector<vector<int>> arr) : n(n), ans(0), parent(n), l(n), size(n, 1),
min1(n, inf), min2(n, inf),
specialMin1(n, inf), specialMin2(n, inf),
sum(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
int a = arr[i][1], b = arr[i][2];
(i % 2 == 0 ? min1 : min2)[i] = a - b;
l[i] = i;
ans += a;
sum[i] = b;
}
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
ll contrib(int x) {
bool even = l[x] % 2 == 0;
return sum[x] + (size[x] % 2 == 1 ? min(even ? min1[x] : min2[x], even ? specialMin2[x] : specialMin1[x]) : 0);
}
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];
l[a] = min(l[a], l[b]);
min1[a] = min(min1[a], min1[b]);
min2[a] = min(min2[a], min2[b]);
specialMin1[a] = min(specialMin1[a], specialMin1[b]);
specialMin2[a] = min(specialMin2[a], specialMin2[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);
priority_queue<pii, vector<pii>, decltype(comp)> pq2(comp);
for (int i = 0; i < n - 1; i++) {
pq.push({i, arr[i + 1][0] - arr[i][0]});
}
for (int i = 1; i < n - 1; i++) {
pq2.push({i, arr[i + 1][0] - arr[i - 1][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);
}
while (!pq2.empty() && pq2.top().second <= d) {
int i = pq2.top().first;
pq2.pop();
int rep = dsu.find(i);
dsu.ans -= dsu.contrib(rep);
vector<int>& specialMin = i % 2 == 0 ? dsu.specialMin1 : dsu.specialMin2;
specialMin[rep] = min(specialMin[rep], arr[i][1] - arr[i][2]);
dsu.ans += dsu.contrib(rep);
}
ans[j] = dsu.ans;
}
return ans;
}
