#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> f, mn, ev, od;
long long s;
DSU(int n) {
f.resize(n, -1);
ev.resize(n, -1e9);
od.resize(n, -1e9);
mn.resize(n);
iota(mn.begin(), mn.end(), 0);
s = 0;
}
void set(int i, int x) {
if (i & 1) {
od[i] = x;
} else {
ev[i] = x;
}
}
int find(int u) {
return f[u] < 0 ? u : f[u] = find(f[u]);
}
void upd(int i, int x) {
int u = find(i);
if (f[u] & 1) {
s -= ((mn[u] & 1) ? od[u] : ev[u]);
}
if (i & 1) {
od[u] = max(od[u], x);
} else {
ev[u] = max(ev[u], x);
}
if (f[u] & 1) {
s += ((mn[u] & 1) ? od[u] : ev[u]);
}
}
void unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (f[u] > f[v]) swap(u, v);
if (f[u] != -1 && (f[u] & 1)) {
s -= ((mn[u] & 1) ? od[u] : ev[u]);
}
if (f[v] != -1 && (f[v] & 1)) {
s -= ((mn[v] & 1) ? od[v] : ev[v]);
}
f[u] += f[v];
f[v] = u;
mn[u] = min(mn[u], mn[v]);
od[u] = max(od[u], od[v]);
ev[u] = max(ev[u], ev[v]);
if (f[u] & 1) {
s += ((mn[u] & 1) ? od[u] : ev[u]);
}
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = w.size();
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](const int &i, const int &j) {
return w[i] < w[j];
});
auto tw = w, ta = a, tb = b;
for (int i = 0; i < n; i++) {
w[i] = tw[id[i]];
a[i] = ta[id[i]];
b[i] = tb[id[i]];
}
vector<pair<int, int>> q, q2;
for (int i = 0; i + 1 < n; i++) {
q.push_back({w[i + 1] - w[i], i});
}
for (int i = 0; i + 2 < n; i++) {
q2.push_back({w[i + 2] - w[i], i});
}
sort(q.begin(), q.end());
sort(q2.begin(), q2.end());
DSU ds(n);
long long ss = 0;
for (int i = 0; i < n; i++) {
ss += a[i];
ds.set(i, b[i] - a[i]);
}
int m = e.size();
vector<pair<int, int>> ne(m);
for (int i = 0; i < m; i++) {
ne[i] = {e[i], i};
}
sort(ne.begin(), ne.end());
vector<long long> ans(m);
vector<bool> vis(n);
for (int i = 0, j = 0, k = 0; i < m; i++) {
while (j + 1 < n && q[j].first <= ne[i].first) {
ds.unite(q[j].second, q[j].second + 1);
if (!vis[q[j].second]) {
vis[q[j].second] = 1;
ss += b[q[j].second] - a[q[j].second];
}
if (!vis[q[j].second + 1]) {
vis[q[j].second + 1] = 1;
ss += b[q[j].second + 1] - a[q[j].second + 1];
}
j++;
}
while (k + 2 < n && q2[k].first <= ne[i].first) {
ds.upd(q2[k].second, b[q2[k].second + 1] - a[q2[k].second + 1]);
k++;
}
ans[ne[i].second] = ss - ds.s;
}
return ans;
}
