#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "nile.h"
struct DSU {
const int INF = 1e9;
int n;
vector<int> parent_or_size;
vector<int> L, mn0, mn1, mn2;
ll cur;
DSU() : n(0), cur(0) {}
DSU(const vector<int> &c) { init(c); }
void init(const vector<int> &c) {
n = c.size();
parent_or_size.assign(n, -1);
L.resize(n);
mn0.assign(n, INF);
mn1.assign(n, INF);
mn2.assign(n, INF);
cur = 0;
for (int i = 0; i < n; ++i) {
L[i] = i;
if (i & 1)
mn1[i] = c[i];
else
mn0[i] = c[i];
cur += c[i];
}
}
int leader(int a) {
return parent_or_size[a] < 0
? a
: parent_or_size[a] = leader(parent_or_size[a]);
}
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int a) { return -parent_or_size[leader(a)]; }
int best(int a) {
a = leader(a);
if (size(a) & 1 ^ 1)
return 0;
int res = (L[a] & 1 ^ 1 ? mn0[a] : mn1[a]);
res = min(res, mn2[a]);
return res;
}
int merge(int a, int b) {
a = leader(a), b = leader(b);
if (a == b)
return a;
cur -= best(a);
cur -= best(b);
if (L[a] > L[b])
swap(a, b);
parent_or_size[a] += parent_or_size[b];
parent_or_size[b] = a;
L[a] = min(L[a], L[b]);
mn0[a] = min(mn0[a], mn0[b]);
mn1[a] = min(mn1[a], mn1[b]);
mn2[a] = min(mn2[a], mn2[b]);
cur += best(a);
return a;
}
void enable(int x, int val) {
x = leader(x);
cur -= best(x);
mn2[x] = min(mn2[x], val);
cur += best(x);
}
};
struct Item {
int w, a, b, c;
};
struct Event {
int d, t, i;
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B,
vector<int> E) {
int n = W.size();
int q = E.size();
vector<Item> v(n);
for (int i = 0; i < n; ++i) {
v[i] = {W[i], A[i], B[i], A[i] - B[i]};
}
sort(v.begin(), v.end(),
[&](const Item &x, const Item &y) { return x.w < y.w; });
vector<int> w(n), c(n);
ll base = 0;
for (int i = 0; i < n; ++i) {
w[i] = v[i].w;
c[i] = v[i].c;
base += v[i].b;
}
vector<Event> ev;
for (int i = 0; i + 1 < n; ++i) {
ev.push_back({w[i + 1] - w[i], 0, i});
}
for (int i = 0; i + 2 < n; ++i) {
ev.push_back({w[i + 2] - w[i], 1, i});
}
sort(ev.begin(), ev.end(), [&](const Event &x, const Event &y) {
return (x.d != y.d ? x.d < y.d : x.t < y.t);
});
vector<pair<int, int>> qs(q);
for (int i = 0; i < q; ++i) {
qs[i] = {E[i], i};
}
ranges::sort(qs);
DSU dsu(c);
vector<ll> ans(q);
int ptr = 0;
for (auto [D, id] : qs) {
while (ptr < ev.size() && ev[ptr].d <= D) {
int i = ev[ptr].i;
if (!ev[ptr].t) {
dsu.merge(i, i + 1);
} else {
dsu.enable(i + 1, c[i + 1]);
}
++ptr;
}
ans[id] = base + dsu.cur;
}
return ans;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
//
// auto ans = calculate_costs({15, 12, 2, 10, 21}, {5, 4, 5, 6, 3},
// {1, 2, 2, 3, 2}, {5, 9, 1});
//
// for (auto a : ans) {
// cout << a << " ";
// }
//
// return 0;
// }
