#include <bits/stdc++.h>
using namespace std;
struct torta
{
long long int a,b,w;
};
struct que
{
int k,id;
};
vector<torta>v,g;
vector<que>q;
vector<long long int>dsu,ssum,smax1,smax2,sz,ans;
long long int res=0;
long long int gsum(int i)
{
if(sz[i]%2==0)
{
return ssum[i];
}
return ssum[i]-smax1[i];
}
int vfind(int a)
{
if(a==dsu[a])return a;
return dsu[a]=(vfind(dsu[a]));
}
bool cmp(torta &a,torta &b)
{
return a.w<b.w;
}
bool cmp1(que &a,que &b)
{
return a.k<b.k;
}
vector<long long> calculate_costs(vector<int> W,vector<int> A,vector<int> B,vector<int> E)
{
int n,m;
n=W.size();
m=E.size();
torta temp;
que temp1;
for(int i=0;i<n;i++)
{
temp.w=W[i];
temp.a=A[i];
temp.b=B[i];
res+=A[i];
v.push_back(temp);
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<n;i++)
{
if(i>0)
{
temp.a=i-1;
temp.b=i;
temp.w=v[i].w-v[i-1].w;
g.push_back(temp);
}
dsu.push_back(i);
sz.push_back(1);
smax1.push_back(v[i].a-v[i].b);
ssum.push_back(v[i].a-v[i].b);
smax2.push_back(INT_MAX);
if(i>1)
{
temp.b=i-1;
temp.w=v[i].w-v[i-2].w;
g.push_back(temp);
}
}
sort(g.begin(),g.end(),cmp);
ans.resize(m);
for(int i=0;i<m;i++)
{
temp1.k=E[i];
temp1.id=i;
q.push_back(temp1);
}
sort(q.begin(),q.end(),cmp1);
int l=0,l1=0;
while(l<g.size()||l1<q.size())
{
if(l1==q.size())break;
if(l==g.size()||g[l].w>q[l1].k)
{
ans[q[l1].id]=res;
l1++;
continue;
}
if(g[l].a==g[l].b)
{
int a=vfind(g[l].a);
res=res+gsum(a);
smax1[a]=min(smax1[a],v[g[l].a].a-v[g[l].a].b);
smax2[a]=min(smax2[a],v[g[l].a].a-v[g[l].a].b);
res=res-gsum(a);
}
else
{
int a=vfind(g[l].a),b=vfind(g[l].b);
res=res+gsum(a);
res=res+gsum(b);
dsu[b]=a;
if(sz[a]%2==0)
{
smax1[a]=min(smax1[a],smax1[b]);
smax2[a]=min(smax2[a],smax2[b]);
}
else
{
smax1[a]=min(smax1[a],smax2[b]);
smax2[a]=min(smax2[a],smax1[b]);
}
sz[a]+=sz[b];
ssum[a]+=ssum[b];
res=res-gsum(a);
}
l++;
}
return ans;
}
