#include<bits/stdc++.h>
#define TIME (1.0* clock()/CLOCKS_PER_SEC)
#define pb push_back
#define eb emplace_back
#define id1 (id<<1)
#define id2 (id<<1)|1
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<long long>
#define vll vector <pair<ll,ll>>
#define li pair<long long,int>
#define vil vector <pair<int,ll>>
#define db double
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i <=(b); i++)
#define F0R(i, a) FOR(i, 0, a-1)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)
#define ALL(x) (x).begin(),(x).end()
#define pq priority_queue <li, vector <li>, greater <li>>
using namespace std;
const int maxn = 1e6;
const ll INF = 1e18;
struct DSU {
vl p, sz, m, od, ev, mn, sm;
ll total = 0;
DSU(ll n, const vl& v) {
p.resize(n + 1); iota(ALL(p), 0);
sz.assign(n + 1, 1);
m.assign(n, INF);
od.assign(n, INF);
mn.assign(n, INF);
ev = v; sm = v;
}
ll find(ll u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void join(ll u, ll v) {
u = find(u); v = find(v);
if (u == v) return;
swap(u, v);
total -= sm[u] + sm[v];
if (sz[u] == 1) total += sm[u];
if (sz[v] == 1) total += sm[v];
if ((sz[u] & 1) && sz[u] >= 3) total += mn[u];
if ((sz[v] & 1) && sz[v] >= 3) total += mn[v];
if (sz[v] & 1) {
od[v] = min(od[v], ev[u]);
ev[v] = min(ev[v], od[u]);
} else {
od[v] = min(od[v], od[u]);
ev[v] = min(ev[v], ev[u]);
}
sz[v] += sz[u];
p[u] = v;
sm[v] += sm[u];
total += sm[v];
m[v] = min(m[v], m[u]);
mn[v] = min(ev[v], m[v]);
if (sz[v] & 1) total -= mn[v];
}
void update(int u, int v, const vl& w) {
ll r = find(v), d = w[min(u, v) + 1];
m[r] = min(m[r], d);
if (mn[r] > m[r]) {
if (sz[r] & 1) total += mn[r] - m[r];
mn[r] = m[r];
}
}
};
vl calculate_costs(vi w, vi a, vi b, vi e) {
ll n = w.size(), q = e.size(), base = 0;
vl res(ALL(e)); sort(ALL(e));
vector<array<ll, 2>> dif(n);
F0R(i, n) {
base += a[i];
dif[i] = {w[i], (ll)a[i] - b[i]};
}
sort(ALL(dif));
vector<array<ll, 3>> g1, g2;
F0R(i, n - 1) {
g1.pb({dif[i + 1][0] - dif[i][0], i, i + 1});
if (i < n - 2) g2.pb({dif[i + 2][0] - dif[i][0], i, i + 2});
}
vl val(n);
F0R(i, n) val[i] = dif[i][1];
DSU dsu(n, val);
sort(ALL(g1)); sort(ALL(g2));
map<ll, ll> mp;
ll i1 = 0, i2 = 0;
F0R(i, q) {
while (i1 < n - 1 && e[i] >= g1[i1][0]) {
dsu.join(g1[i1][1], g1[i1][2]);
i1++;
}
while (i2 < n - 2 && e[i] >= g2[i2][0]) {
dsu.update(g2[i2][1], g2[i2][2], val);
i2++;
}
mp[e[i]] = base - dsu.total;
}
F0R(i, q) res[i] = mp[res[i]];
return res;
}
