#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int res=0;
vector<int> dsu, all, l, r;
vector<multiset<int> > odd, even;
vector<pair<int, pii> > vect;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
void merge(int a, int b){
a=fp(a), b=fp(b);
if (a==b)return;
res-=min(all[a], *odd[a].begin())+min(all[b], *odd[b].begin());
if (l[a]>l[b])swap(a, b);
if (l[a]%2!=r[a]%2){
if (odd[a].size()<odd[b].size())swap(odd[a], odd[b]);
for (auto c:odd[b])odd[a].insert(c);
if (even[a].size()<even[b].size())swap(even[a], even[b]);
for (auto c:even[b])even[a].insert(c);
}
else{
if (odd[a].size()<even[b].size())swap(odd[a], even[b]);
for (auto c:even[b])odd[a].insert(c);
if (even[a].size()<odd[b].size())swap(even[a], odd[b]);
for (auto c:odd[b])even[a].insert(c);
}
all[a]=min(all[a], all[b]);
r[a]=r[b];
dsu[b]=a;
res+=min(all[a], *odd[a].begin());
}
void changeover(int i){
res-=min(all[fp(i)], *odd[fp(i)].begin());
if (l[fp(i)]%2==i%2)odd[fp(i)].erase(odd[fp(i)].lower_bound(vect[i].se.fi-vect[i].se.se));
else even[fp(i)].erase(even[fp(i)].lower_bound(vect[i].se.fi-vect[i].se.se));
all[fp(i)]=min(all[fp(i)], vect[i].se.fi-vect[i].se.se);
res+=min(all[fp(i)], *odd[fp(i)].begin());
}
vector<int> calculate_costs(vector<signed> w, vector<signed> a, vector<signed> b, vector<signed> e){
int n=w.size(), p=0;
vector<int> ans(e.size());
vector<pii> query(e.size());
vect.resize(n);
l.resize(n);
r.resize(n);
odd.resize(n);
even.resize(n);
all.resize(n, LLONG_MAX/2);
dsu.resize(n, -1);
for (int i=0; i<e.size(); ++i)query[i]=mp(e[i], i);
sort(query.begin(), query.end());
for (int i=0; i<n; ++i)vect[i]=mp(w[i], mp(a[i], b[i])), res+=a[i];
sort(vect.begin(), vect.end());
for (int i=0; i<n; ++i)odd[i].insert(vect[i].se.fi-vect[i].se.se), l[i]=r[i]=i;
vector<pair<int, pii> > ord;
for (int i=1; i<n; ++i)ord.pb(mp(vect[i].fi-vect[i-1].fi, mp(i, i-1)));
for (int i=2; i<n; ++i)ord.pb(mp(vect[i].fi-vect[i-2].fi, mp(-1, i-1)));
sort(ord.begin(), ord.end());
for (auto c:query){
while (p<ord.size()&&ord[p].fi<=c.fi){
if (ord[p].se.fi==-1)changeover(ord[p].se.se);
else merge(ord[p].se.fi, ord[p].se.se);
++p;
}
ans[c.se]=res;
}
return ans;
}
