#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
/*ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout*/
const int MAXN=1e5+10;
typedef long long ll;
const ll INF=1e18;
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;
};
vector<dif> d;
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[2][MAXN],sum[MAXN],l[MAXN],dmine[2][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);
ll dcrt[2],dcrte[2];
if (s[x]%2){
dcrt[0]=min (dmin[0][x],dmin[1][y]);
dcrt[1]=min (dmin[1][x],dmin[0][y]);
dcrte[0]=min (dmine[0][x],dmine[1][y]);
dcrte[1]=min (dmine[1][x],dmine[0][y]);
}
else{
dcrt[0]=min (dmin[0][x],dmin[0][y]);
dcrt[1]=min (dmin[1][x],dmin[1][y]);
dcrte[0]=min (dmine[0][x],dmine[0][y]);
dcrte[1]=min (dmine[1][x],dmine[1][y]);
}
if (s[x]<s[y]) swap (x,y);
rez-=sum[x];
rez-=sum[y];
l[x]=min (l[x],l[y]);
s[x]+=s[y];
tata[y]=x;
sumc2[x]+=sumc2[y];
dmin[0][x]=dcrt[0];
dmin[1][x]=dcrt[1];
dmine[0][x]=dcrte[0];
dmine[1][x]=dcrte[1];
if (s[x]%2==0) sum[x]=sumc2[x];
else sum[x]=sumc2[x]+min (dmin[1][x],dmine[0][x]);
rez+=sum[x];
}
void enable (int x){
int r=radacina (x);
if ((x-l[r])%2==0) dmine[1][r]=min (dmine[1][r],1LL*a[x].c1-a[x].c2);
else dmine[0][r]=min (dmine[0][r],1LL*a[x].c1-a[x].c2);
rez-=sum[r];
if (s[r]%2) sum[r]=sumc2[r]+min (dmin[1][r],dmine[0][r]);
rez+=sum[r];
}
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.push_back ({a[i+1].w-a[i].w,i,i+1});
if (i<n-1) d.push_back ({a[i+2].w-a[i].w,i,i+2});
}
sort (d.begin (),d.end (),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;
dmine[0][i]=dmine[1][i]=INF;
dmin[0][i]=INF;
dmin[1][i]=a[i].c1-a[i].c2;
l[i]=i;
}
int j=0;
for (int i=1;i<=m;++i){
while (j<d.size () and q[i].x>=d[j].x){
if (d[j].l+1==d[j].r) unire (d[j].l,d[j].r);
else enable (d[j].l+1);
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;
for (int i=1;i<=n;++i){
int x,y,z;
cin >>x>>y>>z;
W.push_back (x);
A.push_back (y);
B.push_back (z);
}
cin >>q;
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<<'\n';
}
return 0;
}*/
/*
15 12 2 10 21
5 4 5 6 3
1 2 2 3 2
5 9 1
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
*/
