#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e17;
struct item{
int w;
int a,b;
inline friend bool operator < (item fr,item sc){
return fr.w<sc.w;
}
};
int delta;
int n;
item a[MAXN];
vector< pair<int,int> > raz,qs;
long long ans[MAXN];
struct Segment_Tree{
struct node{
int len;
long long ans[3][3];
void fills(int x){
for(int i=0;i<3;i++){
for(int f=0;f<3;f++){
ans[i][f]=x;
}
}
}
long long mins(int l,int r){
long long res=inf;
for(int i=l;i<3;i++){
for(int f=r;f<3;f++){
res=min(res,ans[i][f]);
}
}
return res;
}
};
node tree[4*MAXN];
node combine(vector<item> mids,node fr,node sc,int lsz,int rsz,int l,int r){
node res;
res.len=fr.len+sc.len;
long long sum=0;
for(auto s:mids){
sum+=s.a;
}
if(r-l+1>=4){
for(int i=0;i<3;i++){
for(int f=0;f<3;f++){
res.ans[i][f]=fr.mins(i,0) + sc.mins(0,f);
if(i+f>res.len)res.ans[i][f]=inf;
if(abs(mids[0].w-mids[1].w)<=delta)res.ans[i][f]=min(res.ans[i][f] , fr.mins(i,1) + sc.mins(1,f) - mids[0].a-mids[1].a+mids[0].b+mids[1].b);
if(abs(mids[2].w-mids[1].w)<=delta)res.ans[i][f]=min(res.ans[i][f] , fr.mins(i,2) + sc.mins(1,f) - mids[2].a-mids[1].a+mids[2].b+mids[1].b);
if(abs(mids[0].w-mids[3].w)<=delta)res.ans[i][f]=min(res.ans[i][f] , fr.mins(i,1) + sc.mins(2,f) - mids[0].a-mids[3].a+mids[0].b+mids[3].b);
}
}
}else{
for(int i=0;i<3;i++){
for(int f=0;f<3;f++){
res.ans[i][f]=sum;
for(int t=l+i;t<=r-f;t++){
for(int k=t+1;k<=r-f;k++){
if(abs(a[k].w-a[t].w)<=delta)res.ans[i][f]=min(res.ans[i][f],sum-a[k].a-a[t].a+a[k].b+a[t].b);
}
}
}
}
}
return res;
}
void update(int v,int l,int r,int pos){
if(l==r){
tree[v].len=1;
tree[v].fills(a[l].a);
return;
}else{
int tt=(l+r)/2;
if(pos<=tt)update(2*v,l,tt,pos);
else update(2*v+1,tt+1,r,pos);
vector<item> z;
z.push_back(a[tt]);
z.push_back(a[tt+1]);
if(tt-1>=l)z.push_back(a[tt-1]);
if(tt+2<=r)z.push_back(z[tt+2]);
tree[v]=combine(z,tree[2*v],tree[2*v+1],tt-l+1,r-tt,l,r);
}
}
void upd(int ind){
for(int i=max(ind-10,1);i<=min(ind+10,n);i++){
update(1,1,n,i);
}
}
}tree;
vector<long long> calculate_costs(vector<int> W, vector<int> A,vector<int> B,vector<int> E){
n=int(W.size());
for(int i=1;i<=n;i++){
a[i]={W[i-1],A[i-1],B[i-1]};
}
sort(a+1,a+n+1);
delta=0;
for(int i=1;i<=n;i++)tree.update(1,1,n,i);
for(int i=1;i<=n;i++){
if(i+1<=n)raz.push_back({a[i+1].w-a[i].w,i});
if(i+2<=n)raz.push_back({a[i+2].w-a[i].w,i});
}
sort(raz.begin(),raz.end());
for(int i=0;i<E.size();i++){
qs.push_back({E[i],i});
}
sort(qs.begin(),qs.end());
int pt=0;
for(int i=0;i<qs.size();i++){
delta=qs[i].first;
while(pt<raz.size() and raz[pt].first<=qs[i].first){
tree.upd(raz[pt].second);
pt++;
}
ans[qs[i].second]=tree.tree[1].ans[0][0];
}
vector<long long> sol;
for(int i=0;i<qs.size();i++)sol.push_back(ans[i]);
return sol;
}
/*int main(){
auto res=calculate_costs({15, 12, 2, 10, 21},
{5, 4, 5, 6, 3},
{1, 2, 2, 3, 2},
{5, 9, 1});
for(auto s:res)cout<<s<<" ";
return 0;
}*/
