#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<int, pair<int, int>>> h;
struct DSU
{
vector<ll> ta, p, mp, im, le, lr, mi0, mi, ns, qh;
DSU (int n)
{
ta.assign(n, 1); p.resize(n); im.resize(n); mp.assign(n, mod); le.resize(n);
mi0.assign(n, mod); ns.resize(n); qh.resize(n); lr.resize(n); mi.resize(n);
for(int i=0; i<n; i++)
{
p[i]=i; le[i]=i; lr[i]=i; im[i]=h[i].S.F-h[i].S.S; mi[i]=h[i].S.F-h[i].S.S;
ns[i]=h[i].S.S; qh[i]=h[i].S.F; tc+=h[i].S.F;
}
}
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; if(le[a]>le[b])swap(a, b);
tc-=qh[a]; tc-=qh[b]; ll me=mp[a], mn=im[a];
if((lr[a]-le[a]+1)%2)
{
me=min(me, im[b]); mn=min(mn, mp[b]);
}
else{me=min(me, mp[b]); mn=min(mn, im[b]);}
ll al=min({mn, mi[a], mi0[b]});
p[b]=a; ta[a]+=ta[b]; le[a]=min(le[a], le[b]); lr[a]=max(lr[a], lr[b]);
mp[a]=me; im[a]=mn; mi[a]=al; ns[a]+=ns[b];mi0[a]=min(mi0[a], mi0[b]);
qh[a]=ns[a];
if((lr[a]-le[a]+1)%2){qh[a]+=mi[a];} 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);
ll y=0;for(int i=0; i<n; i++){y+=b[i];}
for(int i=0; i<n; i++)h[i]={w[i],{a[i], b[i]}};
sort(h.begin(), h.end()); vector<pair<pair<int, int>, pair<int, int>>> q1;
for(int i=0; i<n; i++)
{
if(i+1<n)q1.push_back({{abs(h[i].F-h[i+1].F),0}, {i, i+1}});
}
for(int i=0; i<n; i++)
{
if(i+2<n)q1.push_back({{abs(h[i].F-h[i+2].F), 1}, {i, i+2}});
}
sort(q1.begin(), q1.end());
vector<pair<int, int>> gj(q);
for(int i=0; i<q; i++){gj[i]={e[i], i};} sort(gj.begin(), gj.end());
tc=0; DSU r1(n); int rt=0;
for(int c=0; c<q; c++)
{
while(rt<q1.size()&&q1[rt].F.F<=gj[c].F)
{
if(q1[rt].S.F+1==q1[rt].S.S)r1.uni(q1[rt].S.F, q1[rt].S.S);
else
{
int ux=r1.find(q1[rt].S.F); tc-=r1.qh[ux];
r1.mi[ux]=min(r1.mi[ux],(ll)h[q1[rt].S.F+1].S.F-h[q1[rt].S.F+1].S.S);
r1.mi0[ux]=min(r1.mi0[ux],(ll)h[q1[rt].S.F+1].S.F-h[q1[rt].S.F+1].S.S);
r1.qh[ux]=r1.ns[ux]; if((r1.lr[ux]-r1.le[ux]+1)%2){r1.qh[ux]+=r1.mi[ux];}
tc+=r1.qh[ux];
}
rt++;
}
r[gj[c].S]=tc;
}
return r;
}
