#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
typedef pair<ll,ll> ii;
typedef tuple<ll,ll,ll> tp;
const int M=1e5+10;
const int N=1e3+10;
const int mod=1e9+7;
//
ll q,n,res=0;
struct node
{
ll w,a,b;
}pos[M];
bool cmp (const node &a,const node &b)
{
return a.w<b.w;
}
ii d[M];
// segment tree
struct segment_tree
{
ll t[4*M];
void reset()
{
fori(i,1,4*n) t[i]=1e15;
}
void upd(int s,int l,int r,int pos,ll val)
{
if(l>pos||r<pos) return ;
if(l==r)
{
t[s]=val;
return ;
}
int mid=(l+r)/2;
upd(s*2,l,mid,pos,val);
upd(s*2+1,mid+1,r,pos,val);
t[s]=min(t[s*2],t[s*2+1]);
}
ll get(int s,int l,int r,int u,int v)
{
if(l>v||r<u) return 1e15;
if(u<=l&&r<=v) return t[s];
int mid=(l+r)/2;
return min(get(s*2,l,mid,u,v),get(s*2+1,mid+1,r,u,v));
}
} T[2];
// dsu
ll id[M],val[M],sum[M];
int finded(int u)
{
return id[u]<0 ? u : id[u]=finded(id[u]);
}
void unioned(int u,int v)
{
//cout << u << " " << v << "sa\n";
u=finded(u);
v=finded(v);
id[u]+=id[v];
id[v]=u;
int sz=abs(id[u]);
res-=val[u];
res-=val[v];
if(sz%2) {
val[u]=sum[u+sz-1]-sum[u-1]+T[u%2].get(1,1,n,u,u+sz-1);
res+=val[u];
}
else{
val[u]=sum[u+sz-1]-sum[u-1];
res+=val[u];
}
}
vector<node> edge;
vector<ii> odd;
void pre()
{
fori(i,1,n-1) edge.push_back({pos[i+1].w - pos[i].w,i,i + 1});
fori(i,1,n-2) odd.push_back({pos[i+2].w - pos[i].w,i + 1});
sort(edge.begin(),edge.end(),cmp);
sort(odd.begin(),odd.end());
fori(i,1,n) {
id[i] = -1;
sum[i] = sum[i-1] + pos[i].b;
val[i] += pos[i].a;
res += pos[i].a;
}
fori(i,0,1) T[i].reset();
for(int i = 1;i <= n;i += 2) T[1].upd(1,1,n,i,pos[i].a - pos[i].b);// min
for(int i = 2;i <= n;i += 2) T[0].upd(1,1,n,i,pos[i].a - pos[i].b);
}
ll ret[M];
void solve()
{
int j=0;
int e=0;
fori(i,1,q){
ll w=d[i].first;
int idx=d[i].second;
while(e!=odd.size()&&odd[e].first<=w){
int idx2=odd[e].second;
//cout << idx2 << " " << pos[idx2].b << "a\n";
T[idx2%2==0].upd(1,1,n,idx2,pos[idx2].a-pos[idx2].b);
int u=finded(idx2);
int sz=abs(id[u]);
res-=val[u];
if(sz%2) {
val[u]=sum[u+sz-1]-sum[u-1]+T[u%2].get(1,1,n,u,u+sz-1) ;
res+=val[u];
}
else {
val[u]=sum[u+sz-1]-sum[u-1] ;
res+=val[u];
}
e++;
}
while(j!=edge.size()&&edge[j].w<=w){
unioned(edge[j].a,edge[j].b);
j++;
}
// cout << odd[e].first << " " << w << " " << edge[j].w << "\n";
ret[idx]=res;
}
//fori(i,1,q) cout << ret[i] << "\n";
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
n=W.size();
fori(i,1,n) {
pos[i].w=W[i - 1];
pos[i].a=A[i - 1];
pos[i].b=B[i - 1];
}
sort(pos + 1, pos + n + 1, cmp);
q = E.size();
fori(i,1,q) {
d[i].first = E[i - 1];
d[i].second = i;
}
sort(d+1,d+q+1);
pre();
solve();
vector<long long > R;
fori(i,1,q) R.push_back(ret[i]);
return R;
}
