#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define S second
#define F first
const ll mod=1e18;
ll tc=0;
vector<pair<pair<int, int>, pair<int, int>>> h;
struct DSU
{
vector<ll> mp, im, ns, qh, mi; vector<int> p, ta;
DSU (int n)
{
ta.assign(n, 1); p.resize(n); im.resize(n); mp.assign(n, mod);
ns.resize(n); qh.assign(n, 0); mi.assign(n, mod);
for(int i=0; i<n; i++)
{
p[i]=i; im[i]=h[i].S.F-h[i].S.S; ns[i]=h[i].S.F-h[i].S.S;
}
}
int find(int x)
{
if(p[x]==x)return x; return p[x]=find(x);
}
bool uni(int x, int y)
{
int a=find(x), b=find(y); if(a==b)return false;
tc-=qh[a]; tc-=qh[b]; ll me=min(mp[a], mp[b]), mn=min(im[a], im[b]);
ll uw=ns[a]+ns[b], ik=uw;
if(ta[a]%2)
{
me=min(mp[a], im[b]); mn=min(im[a], mp[b]);
}
if((ta[a]+ta[b])%2){ik=max(uw-mn, uw-min(uw, min(mi[a], mi[b])));}
if(ta[a]<ta[b])swap(a, b);
p[b]=a; ta[a]+=ta[b]; mp[a]=me; im[a]=mn; ns[a]=uw; qh[a]=ik;
mi[a]=min(mi[a], mi[b]); tc+=qh[a];
return true;
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a,vector<int> b, vector<int> e) {
int q = (int)e.size(), n=a.size(); vector<long long> r(q, 0); h.resize(n);
for(int i=0; i<n; i++)h[i]={{w[i],i},{a[i],b[i]}};
ll y=accumulate(a.begin(), a.end(), 0LL);
sort(h.begin(), h.end());
tc=0; DSU r1(n); vector<pair<int, int>> q1; vector<pair<int, int>> q2;
vector<pair<int, int>> gj(q);
for(int i=0; i<q; i++){gj[i]={e[i], i};} sort(gj.begin(), gj.end());
for(int i=0; i<n; i++)
{
if(i+1<n)q1.push_back({h[i+1].F.F-h[i].F.F,i});
}
sort(q1.rbegin(), q1.rend());
for(int i=0; i<n; i++)
{
if(i+2<n)q2.push_back({h[i+2].F.F-h[i].F.F, i});
}
sort(q2.rbegin(), q2.rend());
for(int c=0; c<q; c++)
{
while(!q1.empty()&&q1.back().F<=gj[c].F)
{
r1.uni(q1.back().S, q1.back().S+1); q1.pop_back();
}
while(!q2.empty()&&q2.back().F<=gj[c].F)
{
int ux=r1.find(q2.back().S), ph=h[q2.back().S+1].S.F-h[q2.back().S+1].S.S;
r1.mi[ux]=min(r1.mi[ux],(ll)ph);
if(r1.ta[ux]%2)
{
tc-=r1.qh[ux]; r1.qh[ux]=max(r1.qh[ux], r1.ns[ux]-min(r1.ns[ux],(ll)ph));
tc+=r1.qh[ux];
}q2.pop_back();
}
r[gj[c].S]=y-tc;
}
return r;
}
