#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
#define el '\n'
const int N = 1e6 + 24;
struct Node {
ll w, a, b;
};
struct Edge {
int u, v; ll w;
Edge() {};
Edge(int u_, int v_, ll w_): u(u_), v(v_), w(w_) {}
};
vector<int> par, sz, ch, le;
vector<ll> sum, mn, even, odd;
Node p[N]; ll pf[N];
void init(int n) {
par.resize(n + 1); sz.resize(n + 1);
ch.resize(n + 1); le.resize(n + 1);
mn.resize(n + 1); sum.resize(n + 1);
even.resize(n + 1), odd.resize(n + 1);
for (int i = 1; i <= n; i++) {
par[i] = i, sz[i] = 1, ch[i] = i % 2, le[i] = i;
odd[i] = even[i] = mn[i] = 1e18;
}
}
int find(int v) {
return (v == par[v] ? v : par[v] = find(par[v]));
}
bool join(int u, int v, ll d) {
u = find(u), v = find(v);
if (u != v) {
if (sz[u] < sz[v]) swap(u, v);
mn[u] = min(mn[u], mn[v]);
odd[u] = min(odd[u], odd[v]);
even[u] = min(even[u], even[v]);
le[u] = min(le[u],le[v]);
if ((sz[u] + sz[v]) % 2 == 1) {
if (le[u] % 2 == 0) {
ch[u] = 0;
}
else {
ch[u] = 1;
}
}
par[v] = u;
sz[u] += sz[v];
sum[u] += sum[v];
return 1;
}
else return 0;
}
ll cost(int u) {
u = find(u);
if (sz[u] % 2 == 0) return sum[u];
else {
if (ch[u] == 0) return sum[u] + min(even[u], mn[u]);
return sum[u] + min(odd[u], mn[u]);
}
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size(); init(n);
for (int i = 1; i <= n; i++) {
p[i].w = W[i - 1];
p[i].a = A[i - 1];
p[i].b = B[i - 1];
}
sort(p + 1, p + n + 1, [](Node x, Node y) { return x.w < y.w; });
for (int i = 1; i <= n; i++) {
sum[i] = p[i].b;
if (i % 2 == 1) odd[i] = p[i].a - p[i].b;
else even[i] = p[i].a - p[i].b;
}
for (int i = 1; i <= n; i++) pf[i] = pf[i - 1] + p[i].a;
int q = E.size();
vector<pair<int, int>> qr;
for (int i = 0; i < q; i++) {
qr.push_back({E[i],i});
}
sort(qr.begin(), qr.end());
vector<Edge> e, e2;
for (int i = 2; i <= n; i++) {
e.push_back(Edge(i, i - 1, p[i].w - p[i - 1].w));
}
for (int i = 3; i <= n; i++) {
e2.push_back(Edge(i, i - 2, p[i].w - p[i - 2].w));
}
sort(e.begin(), e.end(), [](Edge a, Edge b) { return a.w < b.w; });
sort(e2.begin(), e2.end(), [](Edge a, Edge b) { return a.w < b.w; });
vector<ll> R(q);
int i = 0, i2 = 0; ll res = 0;
for (int i = 1; i <= n; i++) res += p[i].a;
for (int j = 0; j < q; j++) {
while (i < e.size() && e[i].w <= qr[j].first) {
if (find(e[i].u) != find(e[i].v)) {
res -= cost(e[i].u);
res -= cost(e[i].v);
join(e[i].u, e[i].v, qr[j].first);
res += cost(e[i].u);
}
i++;
}
while (i2 < e2.size() && e2[i2].w <= qr[j].first) {
res -= cost(e2[i2].u);
mn[find(e2[i2].u - 1)] = min(mn[find(e2[i2].u - 1)], p[e2[i2].u - 1].a - p[e2[i2].u - 1].b);
res += cost(e2[i2].u);
i2++;
}
R[qr[j].second] = res;
}
return R;
}
