#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()
using Edge = array<ll, 3>;
const ll inf = 9e18;
struct DSU{
int n, cur;
vector<ll> parent, odd, even, oth, sz, cost;
DSU (int n, vector<ll> cost) : n(n), cost(cost), even(cost){
odd.resize(n, inf); oth.resize(n, inf); sz.resize(n, 1);
parent.resize(n); iota(entire(parent), 0);
cur = accumulate(entire(cost), 0ll);
}
int pi(int u){
return (parent[u] == u) ? u : (parent[u] = pi(parent[u]));
}
void merge (int u, int v){
int pu = pi(u), pv = pi(v), delta;
if (pu == pv) return;
if (pv < pu) swap(pu, pv);
delta = (sz[pu] % 2) * min(oth[pu], even[pu]) + (sz[pv] % 2) * min(oth[pv], even[pv]);
parent[pv] = pu; oth[pu] = min(oth[pu], oth[pv]);
if (sz[pu] % 2 == 0){
even[pu] = min(even[pu], even[pv]);
odd[pu] = min(odd[pu], odd[pv]);
} else {
even[pu] = min(even[pu], odd[pv]);
odd[pu] = min(odd[pu], even[pv]);
} sz[pu] += sz[pv];
delta -= (sz[pu] % 2) * min(oth[pu], even[pu]); cur -= delta;
}
void free(int u){
int p = pi(u), delta;
delta = (sz[p] % 2) * min(oth[p], even[p]);
oth[p] = min(oth[p], cost[u]);
delta -= (sz[p] % 2) * min(oth[p], even[p]);
cur -= delta;
}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> qn){
int n = (ll) A.size(), q = (ll) qn.size();
vector<pii> a(n);
for (int i = 0; i < n; i++) a[i] = pii{W[i], A[i] - B[i]};
sort(entire(a));
ll base = accumulate(entire(B), 0ll);
vector<ll> cost(n);
for (int i = 0; i < n; i++) cost[i] = a[i].ss;
DSU dsu(n, cost);
vector<ll> r(q);
vector<pii> qs(q), edge;
for (int i = 0; i < q; i++) qs[i].ff = qn[i], qs[i].ss = i;
sort(entire(qs));
vector<Edge> sedge;
for (int i = 0; i < n-1; i++){
int idx = edge.size();
edge.push_back(pii{i, i+1});
sedge.push_back(Edge{a[i+1].ff - a[i].ff, 0, idx});
}
for (int i = 0; i < n-2; i++){
int idx = edge.size();
edge.push_back(pii{i, i+2});
sedge.push_back(Edge{a[i+2].ff - a[i].ff, 1, idx});
} sort(entire(sedge));
int ne = sedge.size(), i = 0;
for (auto [d, idx] : qs){
while (i < ne and sedge[i][0] <= d){
auto [u, v] = edge[sedge[i][2]];
if (sedge[i][1] == 0) dsu.merge(u, v);
else dsu.free(min(u, v) + 1);
i++;
} r[idx] = base + dsu.cur;
}
return r;
}
