#include<bits/stdc++.h>
#include"nile.h"
#define MAXN (ll)1e5+5
typedef long long ll;
using namespace std;
//ovaj sam uradio ranije od slanja nego sam ga slao na qoj ac a ne ovde
ll n,q,p[MAXN],v[MAXN],lg[MAXN],c[MAXN],sg[4*MAXN],pb[MAXN];
array<ll,2>e[MAXN],g[MAXN],t[MAXN][25];
array<ll,3> s[MAXN];
vector<ll>r;
ll minq(ll l,ll r,ll j){
ll o=lg[r-l+1];
return min(t[l][o][j],t[r-(1<<o)+1][o][j]);
}
void update(ll l,ll r,ll i,ll x,ll u=1){
if(l>i||r<i||r<l){return;}
if(l==i&&i==r){
sg[u]=x;return;
}
ll m=(l+r)/2;
update(l,m,i,x,2*u);
update(m+1,r,i,x,2*u+1);
sg[u]=min(sg[2*u],sg[2*u+1]);
}ll query(ll l,ll r,ll tl,ll tr,ll u=1){
if(tr<l||r<tl||r<l){return 1e18;}
if(tl<=l&&r<=tr){
return sg[u];
}
ll m=(l+r)/2;
return min(query(l,m,tl,tr,2*u),query(m+1,r,tl,tr,2*u+1));
}
ll find(ll x){
return p[x]=(p[x]==x?x:find(p[x]));
}
ll z=0;
void updc(ll a){
z-=c[a];
c[a]=pb[g[a][1]]-pb[g[a][0]-1]+(v[a]%2)*min(minq(g[a][0],g[a][1],g[a][0]%2),query(1,n,g[a][0],g[a][1]));
z+=c[a];
}
void unite(ll a,ll b){
a=find(a);
b=find(b);
if(a==b){return;}
if(v[a]<v[b]){swap(a,b);}
v[a]+=v[b];
z-=c[b];
p[b]=a;
g[a]={min(g[a][0],g[b][0]),max(g[a][1],g[b][1])};
updc(a);
}
void solve(){
sort(s+1,s+n+1);
sort(e,e+q);
for(ll i=1;i<=n;i++){
update(1,n,i,1e18);
pb[i]=pb[i-1]+s[i][2];
p[i]=i;
c[i]=s[i][1];
z+=c[i];
g[i]={i,i};
v[i]=1;
t[i][0][i%2]=s[i][1]-s[i][2];
t[i][0][!(i%2)]=1e18;
}
update(1,n,1,s[1][1]-s[1][2]);
update(1,n,n,s[n][1]-s[n][2]);
for(ll j=1;j<=lg[n];j++){
for(ll i=1;i+(1<<(j-1))<=n;i++){
t[i][j][0]=min(t[i][j-1][0],t[i+(1<<(j-1))][j-1][0]);
t[i][j][1]=min(t[i][j-1][1],t[i+(1<<(j-1))][j-1][1]);
}
}
priority_queue<array<ll,2>>pq1,pq2;
for(ll i=1;i<=n-1;i++){
pq1.push({-s[i+1][0]+s[i][0],i});
}for(ll i=1;i<=n-2;i++){
pq2.push({-s[i+2][0]+s[i][0],i});
}
for(ll l=0;l<q;l++){
ll d=e[l][0];
while(!pq1.empty()&&d>=-(pq1.top())[0]){
ll i=(pq1.top())[1];pq1.pop();
unite(i,i+1);
}while(!pq2.empty()&&d>=-pq2.top()[0]){
ll i=(pq2.top())[1]+1;pq2.pop();
update(1,n,i,s[i][1]-s[i][2]);
updc(find(i));
}
r[e[l][1]]=z;
}
}
std::vector<ll> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
q = (ll)E.size();
n = (ll)W.size();
lg[0]=lg[1]=0;
for(ll i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
for(ll i=0;i<n;i++){
s[i+1]={W[i],A[i],B[i]};
}for(ll i=0;i<q;i++){
e[i]={E[i],i};
}
r.resize(q,0);
solve();
return r;
}
