#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
struct DSU
{
vector<int> e, mn, sum;
vector<array<int, 2>> pos;
void init(int n)
{
e.assign(n, -1);
sum.assign(n, 0);
mn.assign(n, inf);
pos.assign(n, {inf, inf});
}
int get(int x)
{
if (e[x] < 0) return x;
return e[x] = get(e[x]);
}
int getsum(int x)
{
x = get(x);
if ((-e[x]) & 1) return sum[x] + min(mn[x], pos[x][0]);
else return sum[x];
}
void upd(int x, int val)
{
mn[get(x)] = min(mn[get(x)], val);
}
void unite(int x, int y)
{
x = get(x), y = get(y);
if (x == y) return;
array<int, 2> nw = pos[x];
nw[0] = min(nw[0], pos[y][(-e[x]) & 1]), nw[1] = min(nw[1], pos[y][(-e[x] + 1) & 1]);
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
sum[x] += sum[y];
mn[x] = min(mn[x], mn[y]);
pos[x] = nw;
e[y] = x;
}
};
vector<long long> calculate_costs(vector<int32_t> W, vector<int32_t> A, vector<int32_t> B, vector<int32_t> E)
{
vector<array<int, 3>> w;
vector<array<int, 2>> q;
vector<array<int, 2>> un, ed;
for (int i = 0; i < W.size(); i++) w.push_back({W[i], A[i], B[i]});
for (int i = 0; i < E.size(); i++) q.push_back({E[i], i});
int n = w.size(), Q = q.size();
sort(w.begin(), w.end()), sort(q.begin(), q.end());
for (int i = 1; i + 1 < w.size(); i++) un.push_back({w[i + 1][0] - w[i - 1][0], i});
for (int i = 0; i + 1 < w.size(); i++) ed.push_back({w[i + 1][0] - w[i][0], i});
sort(un.begin(), un.end()), sort(ed.begin(), ed.end());
DSU dsu;
dsu.init(n);
int res = 0;
for (int i = 0; i < n; i++) dsu.sum[i] = w[i][2], dsu.pos[i][0] = w[i][1] - w[i][2], res += w[i][1];
vector<int> ans(Q);
for (int i = 0, j = 0, k = 0; i < Q; i++)
{
while (k < ed.size() && ed[k][0] <= q[i][0])
{
res -= dsu.getsum(ed[k][1]) + dsu.getsum(ed[k][1] + 1);
dsu.unite(ed[k][1], ed[k][1] + 1);
res += dsu.getsum(ed[k][1]);
k++;
}
while (j < un.size() && un[j][0] <= q[i][0])
{
res -= dsu.getsum(un[j][1]);
dsu.upd(un[j][1], w[un[j][1]][1] - w[un[j][1]][2]);
res += dsu.getsum(un[j][1]);
j++;
}
ans[q[i][1]] = res;
}
return ans;
}
