#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll,ll>;
#define all(x) (x).begin(),(x).end()
vector<int> W, A, B, E;
vector<ll> P, R;
vector<pi> queries, V, merges;
int N, Q;
ll ans = 0;
priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll>>, greater<tuple<ll,ll,ll>>> removals;
struct group
{
ll l, r;
bool in_use;
multiset<pi> usable;
group() {}
void init(ll idx)
{
l = r = idx;
in_use = 1;
usable.insert({A[V[r].second] - B[V[r].second], l});
if(l != 0 && r != N-1)
{
removals.push({V[r+1].first-V[r-1].first, A[V[r].second] - B[V[r].second], l});
}
}
};
vector<group> gr;
ll fp(ll pos)
{
return (P[pos] == pos ? pos : P[pos] = fp(P[pos]));
}
vector<ll> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E) {
::W = W;
::A = A;
::B = B;
::E = E;
N = W.size();
Q = E.size();
R.resize(Q, 0);
P.resize(N);
gr.resize(N);
iota(all(P), 0);
for(ll q = 0; q < Q; q++) queries.emplace_back(E[q], q);
for(ll i = 0; i < N; i++) V.emplace_back(W[i], i), ans += A[i];
sort(all(V));
sort(all(queries));
for(ll i = 0; i < N; i++) gr[i].init(i);
for(ll i = 0; i < N-1; i++) merges.emplace_back(V[i+1].first-V[i].first, i);
sort(all(merges), greater<pi>());
for(auto [D, q] : queries)
{
// cout << "Query " << q << "\n";
while(!removals.empty())
{
// cout << "Removing " << removals.size() << "\n";
auto [len, delta, idx] = removals.top();
if(len > D) break;
removals.pop();
ll p = fp(idx);
if(gr[p].in_use)
{
ans -= (*gr[p].usable.begin()).first;
}
gr[p].usable.insert({delta, idx});
if(gr[p].in_use)
{
ans += (*gr[p].usable.begin()).first;
}
}
while(!merges.empty() && merges.back().first <= D)
{
//merge shit
ll lg = fp(merges.back().second);
ll rg = fp(merges.back().second+1);
if(gr[lg].in_use)
{
ans -= (*gr[lg].usable.begin()).first;
gr[lg].in_use = 0;
}
if(gr[rg].in_use)
{
ans -= (*gr[rg].usable.begin()).first;
gr[rg].in_use = 0;
}
if(gr[lg].usable.size() > gr[rg].usable.size())
{
//left is bigger
P[rg] = lg;
//merge sets
for(auto e : gr[rg].usable) gr[lg].usable.insert(e);
//remove invalid
if(gr[lg].r != gr[lg].l && V[gr[rg].l].first-V[gr[lg].r-1].first > D)
{
gr[lg].usable.erase(
gr[lg].usable.find(
{A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r}));
}
if(gr[rg].r != gr[rg].l && V[gr[rg].l+1].first-V[gr[lg].r].first > D)
{
gr[lg].usable.erase(
gr[lg].usable.find(
{A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l}));
}
gr[lg].r = max(gr[lg].r, gr[rg].r);
gr[lg].l = min(gr[lg].l, gr[rg].l);
if((gr[lg].r-gr[lg].l)%2 == 0)
{
ans += (*gr[lg].usable.begin()).first;
gr[lg].in_use = 1;
}
}
else
{
//right is bigger
P[lg] = rg;
for(auto e : gr[lg].usable) gr[rg].usable.insert(e);
//remove invalid
if(gr[lg].r != gr[lg].l && V[gr[rg].l].first-V[gr[lg].r-1].first > D)
{
gr[rg].usable.erase(
gr[rg].usable.find(
{A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r}));
}
if(gr[rg].r != gr[rg].l && V[gr[rg].l+1].first-V[gr[lg].r].first > D)
{
gr[rg].usable.erase(
gr[rg].usable.find(
{A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l}));
}
gr[rg].r = max(gr[lg].r, gr[rg].r);
gr[rg].l = min(gr[lg].l, gr[rg].l);
if((gr[rg].r-gr[rg].l)%2 == 0)
{
ans += (*gr[rg].usable.begin()).first;
gr[rg].in_use = 1;
}
}
merges.pop_back();
}
R[q] = ans;
}
return R;
}
