#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<long long> 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);
queries.clear();
for(ll q = 0; q < Q; q++) queries.emplace_back(E[q], q);
V.clear();
for(ll i = 0; i < N; i++) V.emplace_back(W[i], i), ans += A[i];
sort(all(V));
sort(all(queries));
while (!removals.empty()) removals.pop();
merges.clear();
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)
{
while(!removals.empty())
{
auto top = removals.top();
ll len = get<0>(top);
ll delta = get<1>(top);
ll idx = get<2>(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)
{
ll idx_merge = merges.back().second;
ll lg = fp(idx_merge);
ll rg = fp(idx_merge+1);
if (lg == rg) {
merges.pop_back();
continue;
}
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())
{
P[rg] = lg;
for(auto e : gr[rg].usable) gr[lg].usable.insert(e);
if(gr[lg].r != gr[lg].l)
{
if (V[gr[lg].r].first - V[gr[lg].r-1].first > D)
{
auto it = gr[lg].usable.find({A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r});
if (it != gr[lg].usable.end()) {
gr[lg].usable.erase(it);
}
}
}
if(gr[rg].r != gr[rg].l)
{
if (V[gr[rg].l+1].first - V[gr[rg].l].first > D)
{
auto it = gr[lg].usable.find({A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l});
if (it != gr[lg].usable.end()) {
gr[lg].usable.erase(it);
}
}
}
gr[lg].r = gr[rg].r;
if(gr[lg].r - gr[lg].l + 1 > 1 && (gr[lg].r - gr[lg].l) % 2 == 0)
{
ans += (*gr[lg].usable.begin()).first;
gr[lg].in_use = 1;
}
}
else
{
P[lg] = rg;
for(auto e : gr[lg].usable) gr[rg].usable.insert(e);
if(gr[lg].r != gr[lg].l)
{
if (V[gr[lg].r].first - V[gr[lg].r-1].first > D)
{
auto it = gr[rg].usable.find({A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r});
if (it != gr[rg].usable.end()) {
gr[rg].usable.erase(it);
}
}
}
if(gr[rg].r != gr[rg].l)
{
if (V[gr[rg].l+1].first - V[gr[rg].l].first > D)
{
auto it = gr[rg].usable.find({A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l});
if (it != gr[rg].usable.end()) {
gr[rg].usable.erase(it);
}
}
}
gr[rg].l = gr[lg].l;
if(gr[rg].r - gr[rg].l + 1 > 1 && (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;
}
