#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
int dsu[100000];
int dsv[100000];
int siz[100000];
long long sum = 0;
int get(int i) {
if (dsu[i] == i) return i;
return dsu[i] = get(dsu[i]);
}
void merge(int i, int j) {
i = get(i), j = get(j);
if (i == j) return;
if (siz[i] < siz[j]) swap(i, j);
if (siz[i] % 2 == 1 && siz[j] % 2 == 1) sum -= dsv[i] + dsv[j];
else if (siz[i] % 2 == 0 && siz[j] % 2 == 1) sum -= dsv[i] < dsv[j] ? dsv[j] - dsv[i] : 0;
else if (siz[i] % 2 == 1 && siz[j] % 2 == 0) sum -= dsv[j] < dsv[i] ? dsv[i] - dsv[j] : 0;
else sum -= max(dsv[i], dsv[j]);
dsv[i] = min(dsv[i], dsv[j]);
siz[i] += siz[j];
dsu[j] = i;
}
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = w.size(), q = e.size();
vector<pair<int, int>> c(n);
fo(i, 0, n) sum += a[i], c[i] = {w[i], a[i] - b[i]};
sort(be(c));
map<int, vector<int>> ds;
fo(i, 0, q) ds[e[i]].pb(i);
vector<long long> res(q);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dsu[0] = 0, dsv[0] = c[0].s, siz[0] = 1;
fo(i, 1, n) dsu[i] = i, dsv[i] = c[i].s, siz[i] = 1, pq.push({c[i].f - c[i - 1].f, i});
for (auto [d, is] : ds) {
while (pq.size() && pq.top().f <= d) {
auto [diff, i] = pq.top();
pq.pop();
merge(i, i - 1);
}
for (int i : is) res[i] = sum;
}
return res;
}
