#include "nile.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long
using namespace std;
ll P[100000], tot[100000], sz[100000], opt[100000], opt2[100000];
ll dsu(ll u) {
if (P[u] == u) return u;
else return P[u] = dsu(P[u]);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
vector <array<ll, 3> > X, Q;
vector <ll> F;
F.resize(E.size());
ll n = W.size(), f = 0;
for (int i=0; i<n; ++i) {
f += A[i];
X.push_back({W[i], A[i], B[i]});
}
sort(X.begin(), X.end());
for (int i=0; i<n; ++i) P[i] = i, tot[i] = X[i][2], sz[i] = 1, opt[i] = X[i][1]-X[i][2], opt2[i] = 1e18;
for (int i=0; i<n-1; ++i) {
Q.push_back({X[i+1][0]-X[i][0], 0, i});
}
for (int i=0; i<n-2; ++i) {
Q.push_back({X[i+2][0]-X[i][0], -1, i+1});
}
for (int i=0; i<E.size(); ++i) {
Q.push_back({E[i], 1, i});
}
sort(Q.begin(), Q.end());
for (auto [w, ty, u] : Q) {
if (ty == -1) {
ll a = dsu(u);
f -= tot[a] + (sz[a] & 1 ? opt[a] : 0);
opt[a] = min(opt[a], X[u][1]-X[u][2]);
opt2[a] = min(opt2[a], X[u][1]-X[u][2]);
f += tot[a] + (sz[a] & 1 ? opt[a] : 0);
}
else if (ty == 0) {
ll a = dsu(u), b = dsu(u+1);
f -= tot[a] + (sz[a] & 1 ? opt[a] : 0);
f -= tot[b] + (sz[b] & 1 ? opt[b] : 0);
P[a] = b;
if (sz[a] & 1) swap(opt[b], opt2[b]);
opt[b] = min(opt[b], opt[a]);
opt2[b] = min(opt2[b], opt2[a]);
sz[b] += sz[a];
tot[b] += tot[a];
f += tot[b] + (sz[b] & 1 ? opt[b] : 0);
}
else F[u] = f;
}
return F;
}
