#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
const int MAXN=1e5+10;
typedef long long ll;
struct query{
int x,i;
}q[MAXN];
bool cmp3 (query a, query b){
return a.x<b.x;
}
struct artefact{
int w,c1,c2;
}a[MAXN];
bool cmp (artefact x, artefact y){
return x.w<y.w;
}
struct dif{
int x,l,r;
}d[MAXN];
bool cmp2 (dif a, dif b){
return a.x<b.x;
}
int n,m,tata[MAXN],s[MAXN];
ll ans[MAXN],rez,sumc2[MAXN],dmin[MAXN],sum[MAXN];
int radacina (int x){
if (tata[x]==x) return x;
return tata[x]=radacina (tata[x]);
}
void unire (int x, int y){
x=radacina (x),y=radacina (y);
if (s[x]<s[y]) swap (x,y);
rez-=sum[x];
rez-=sum[y];
s[x]+=s[y];
tata[y]=x;
sumc2[x]+=sumc2[y];
dmin[x]=min (dmin[x],dmin[y]);
if (s[x]%2==0) sum[x]=sumc2[x];
else sum[x]=sumc2[x]+dmin[x];
rez+=sum[x];
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E){
n=W.size ();
m=E.size ();
for (int i=0;i<n;++i){
a[i+1].w=W[i];
a[i+1].c1=A[i];
a[i+1].c2=B[i];
}
for (int i=0;i<m;++i){
q[i+1]={E[i],i+1};
}
sort (a+1,a+n+1,cmp);
for (int i=1;i<n;++i){
d[i].x=a[i+1].w-a[i].w;
d[i].l=i;
d[i].r=i+1;
}
sort (d+1,d+n,cmp2);
sort (q+1,q+m+1,cmp3);
for (int i=1;i<=n;++i){
s[i]=1;
tata[i]=i;
rez+=a[i].c1;
sum[i]=a[i].c1;
sumc2[i]=a[i].c2;
dmin[i]=a[i].c1-a[i].c2;
}
int j=1;
for (int i=1;i<=m;++i){
while (j<=n-1 and q[i].x>=d[j].x){
unire (d[j].l,d[j].r);
j++;
}
ans[q[i].i]=rez;
}
vector <ll> aux;
for (int i=1;i<=m;++i){
aux.push_back (ans[i]);
}
return aux;
}
/*signed main()
{
ios_base::sync_with_stdio (false);
cin.tie (nullptr);
vector <int> A,W,B,E;
int n,q;
cin >>n>>q;
for (int i=1;i<=n;++i){
int x;
cin >>x;
W.push_back (x);
}
for (int i=1;i<=n;++i){
int x;
cin >>x;
A.push_back (x);
}
for (int i=1;i<=n;++i){
int x;
cin >>x;
B.push_back (x);
}
for (int i=1;i<=q;++i){
int x;
cin >>x;
E.push_back (x);
}
vector <ll> aux=calculate_costs (W,A,B,E);
for (auto x:aux){
cout <<x<<' ';
}
return 0;
}*/
/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
*/
