#include "nile.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
struct SegTree
{
ll n;
vector<ll> st;
SegTree(ll sz = 0, bool input = false)
{
n = sz;
st.resize((n + 1) << 1, -1e10);
}
void set(ll i, ll val)
{
st[i + n - 1] = val;
}
void build()
{
for (ll i = n - 1; i >= 1; i--)
st[i] = max(st[i << 1], st[i << 1 | 1]);
}
void modify(ll p, ll val)
{
for (st[p += n - 1] = val; p > 1; p >>= 1)
st[p >> 1] = max(st[p], st[p ^ 1]);
}
ll query(ll l, ll r)
{
ll ans = -1e10;
for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, st[l++]);
if (r & 1)
ans = max(ans, st[--r]);
}
return ans;
}
};
const ll N = 1e5 + 5;
array<ll, 3> a[N];
SegTree st[4];
ll relax(ll l, ll r)
{
if ((r - l) & 1) return 0;
return max(st[l & 1].query(l, r), st[((l + 1) & 1) + 2].query(l, r));
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
ll n = W.size(), q = E.size();
for (ll i = 1; i <= n; i++)
a[i] = {W[i - 1], A[i - 1], B[i - 1]};
sort(a + 1, a + n + 1);
pair<ll, ll> qs[q];
for (ll i = 0; i < q; i++)
qs[i] = make_pair(E[i], i);
sort(qs, qs + q);
pair<ll, ll> diff[n - 1];
for (ll i = 0; i < n - 1; i++)
diff[i] = make_pair(a[i + 2][0] - a[i + 1][0], i + 1);
sort(diff, diff + n - 1);
ll ptr = 0, lef[n + 1], rig[n + 1], res = 0;
for (ll i = 1; i <= n; i++)
res += a[i][1];
for (ll i = 1; i <= n; i++)
lef[i] = rig[i] = i;
st[0] = st[1] = st[2] = st[3] = SegTree(n);
for (ll i = 1; i <= n; i++) st[i & 1].set(i, a[i][2] - a[i][1]);
st[0].build();
st[1].build();
vector<ll> ans(q);
if (n == 1)
{
for (ll i = 0; i < q; i++) ans[i] = a[1][1];
return ans;
}
pair<ll, ll> diff1[n - 2];
for (ll i = 2; i < n; i++)
diff1[i - 2] = make_pair(a[i + 1][0] - a[i - 1][0], i);
sort(diff1, diff1 + n - 2);
ll ptr1 = 0;
set<pair<ll, ll>> s;
for (ll i = 1; i <= n; i++) s.insert(make_pair(i, i));
for (auto [d, ind] : qs)
{
while (ptr1 < n - 2 and diff1[ptr1].first <= d)
{
ll i = diff1[ptr1].second;
auto [l, r] = *--s.upper_bound(make_pair(i, 1e9));
res += relax(l, r);
st[(i & 1) + 2].modify(i, a[i][2] - a[i][1]);
res -= relax(l, r);
ptr1++;
}
while (ptr < n - 1 and diff[ptr].first <= d)
{
ll i = diff[ptr].second;
res += relax(lef[i], i) + relax(i + 1, rig[i + 1]);
s.erase(make_pair(lef[i], i));
s.erase(make_pair(i + 1, rig[i + 1]));
rig[lef[i]] = rig[i + 1];
lef[rig[i + 1]] = lef[i];
res -= relax(lef[i], rig[i + 1]);
s.insert(make_pair(lef[i], rig[i + 1]));
ptr++;
}
ans[ind] = res;
}
return ans;
}
