#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.assign(n, mod); mp.resize(n);
ns.resize(n); qh.assign(n, 0); mi.assign(n, mod);
for(int i=0; i<n; i++){p[i]=i;}
}
int find(int x)
{
if(p[x]==x)return x; return p[x]=find(p[x]);
}
void uni(int a, int b)
{
a=find(a); b=find(b); if(a==b)return;
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-me, uw-min(uw, min(mi[a], mi[b])));}
if(ta[a]<ta[b])swap(a, b);
ta[a]+=ta[b];p[b]=a; mp[a]=me; im[a]=mn; ns[a]=uw; qh[a]=ik;
mi[a]=min(mi[a], mi[b]); tc+=qh[a];
}
};
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());
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());
tc=0; DSU r1(n);
for(int i=0; i<n; i++)
{
r1.mp[i]=a[h[i].F.S]-b[h[i].F.S]; r1.im[i]=mod;
r1.ns[i]=a[h[i].F.S]-b[h[i].F.S]; r1.qh[i]=0; r1.mi[i]=mod;
}
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)
{
auto ty=q2.back(); q2.pop_back();
int ux=r1.find(ty.S); ll ph=a[h[ty.S+1].F.S]-b[h[ty.S+1].F.S];
r1.mi[ux]=min(r1.mi[ux],ph);
if(r1.ta[ux]%2)
{
tc-=r1.qh[ux]; r1.qh[ux]=max(r1.qh[ux], r1.ns[ux]-min(r1.ns[ux],ph));
tc+=r1.qh[ux];
}
}
r[gj[c].S]=y-tc;
}
return r;
}
