#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;
}();
struct DSV {
int mi;
int even, odd;
int two;
};
int dsu[100000];
DSV 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 undo(int i) {
if (siz[i] % 2 == 1) sum -= min(dsv[i].mi % 2 == 0 ? dsv[i].even : dsv[i].odd, dsv[i].two);
}
void redo(int i) {
if (siz[i] % 2 == 1) sum += min(dsv[i].mi % 2 == 0 ? dsv[i].even : dsv[i].odd, dsv[i].two);
}
void merge(int i, int j) {
i = get(i), j = get(j);
if (i == j) return;
if (siz[i] < siz[j]) swap(i, j);
undo(i);
undo(j);
dsv[i].mi = min(dsv[i].mi, dsv[j].mi);
dsv[i].even = min(dsv[i].even, dsv[j].even);
dsv[i].odd = min(dsv[i].odd, dsv[j].odd);
dsv[i].two = min(dsv[i].two, dsv[j].two);
siz[i] += siz[j];
dsu[j] = i;
redo(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, pair<int, bool>>, vector<pair<int, pair<int, bool>>>, greater<pair<int, pair<int, bool>>>> pq;
fo(i, 0, n) dsu[i] = i, dsv[i].mi = i, dsv[i].even = i % 2 == 0 ? c[i].s : INT_MAX, dsv[i].odd = i % 2 == 1 ? c[i].s : INT_MAX,
dsv[i].two = INT_MAX, siz[i] = 1;
fo(i, 1, n) pq.push({c[i].f - c[i - 1].f, {i, false}});
fo(i, 2, n) pq.push({c[i].f - c[i - 2].f, {i - 1, true}});
for (auto [d, is] : ds) {
while (pq.size() && pq.top().f <= d) {
auto [diff, v] = pq.top();
auto [i, t] = v;
pq.pop();
if (t) {
undo(get(i));
dsv[i].two = min(dsv[i].two, c[i].s);
redo(get(i));
} else merge(i, i - 1);
}
for (int i : is) res[i] = sum;
}
return res;
}
