#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct dsu {
int n;
vector<int> p, l;
vector<ll> t, j, f;
ll x = 0;
dsu(vector<ll> &a) {
n = a.size();
p.assign(n, 0);
l.assign(n, 1);
t = a;
x = accumulate(a.begin(), a.end(), 0ll);
j.assign(n, INT_MAX);
f.assign(n, INT_MAX);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
void merge(int a, int b) {
if (a > b) swap(a, b);
a = find(a);
b = find(b);
x -= l[a] % 2 * min(t[a], f[a]);
x -= l[b] % 2 * min(t[b], f[b]);
if (l[a] % 2) t[a] = min(t[a], j[b]), j[a] = min(j[a], t[b]);
else t[a] = min(t[a], t[b]), j[a] = min(j[a], j[b]);
f[a] = min(f[a], f[b]);
p[b] = a;
l[a] += l[b];
x += l[a] % 2 * min(t[a], f[a]);
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
vector<long long> ans;
int q = (int) E.size(), n = (int) W.size();
for (int i = 0; i < n; ++i) A[i] -= B[i];
vector<int> o(n);
iota(o.begin(), o.end(), 0);
sort(o.begin(), o.end(), [&](int i, int j) { return W[i] < W[j]; });
vector<ll> w(n), a(n), b(n);
for (int i = 0; i < n; ++i) w[i] = W[o[i]], a[i] = A[o[i]], b[i] = B[o[i]];
set<pair<int, int>> s;
set<tuple<ll, ll, ll>> c;
for (int i = 1; i < n; ++i) s.emplace(w[i] - w[i - 1], i);
for (int i = 2; i < n; ++i) c.emplace(w[i] - w[i - 2], a[i - 1], i - 1);
o.assign(q, 0);
iota(o.begin(), o.end(), 0);
sort(o.begin(), o.end(), [&](int i, int j) { return E[i] < E[j]; });
dsu d(a);
ans.assign(q, 0);
ll wth = 0;
for (int i : b) wth += i;
for (int i = 0; i < q; ++i) {
int e = E[o[i]];
while (s.size() && (*s.begin()).first <= e) {
int x = (*s.begin()).second;
d.merge(x, x - 1);
s.erase(s.begin());
}
while (c.size() && get<0>(*c.begin()) <= e) {
auto [x, y, z] = *c.begin();
c.erase(c.begin());
z = d.find(z);
d.x -= d.l[z] % 2 * min(d.t[z], d.f[z]);
d.f[z] = min(d.f[z], y);
d.x += d.l[z] % 2 * min(d.t[z], d.f[z]);
}
ans[o[i]] = d.x + wth;
}
return ans;
}
