#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],dp[MAXN];
long long slow(int l,int r){
dp[l-1]=0;
for(int i=l;i<=r;i++){
dp[i]=dp[i-1]+a[i].a;
if(i-1>=l and (a[i].w-a[i-1].w)<=delta)dp[i]=min(dp[i],dp[i-2]+a[i].b+a[i-1].b);
if(i-2>=l and (a[i].w-a[i-2].w)<=delta)dp[i]=min(dp[i],dp[i-3]+a[i-2].b+a[i-1].a+a[i].b);
}
return dp[r];
}
struct node{
long long ans[3][3];
};
node tree[4*MAXN];
void solve(int v,int l,int r){
if(r-l+1<=7){
long long pref=0;
for(int i=0;i<3;i++){
long long suff=0;
for(int f=0;f<3;f++){
tree[v].ans[i][f]=slow(l+i,r-f)+pref+suff;
suff+=a[r-f].a;
}
pref+=a[l+i].a;
}
return;
}
int mid=(l+r)/2;
solve(2*v,l,mid);
solve(2*v+1,mid+1,r);
auto s=tree[2*v],t=tree[2*v+1];
for(int i=0;i<3;i++){
for(int f=0;f<3;f++){
long long curr=s.ans[i][0]+t.ans[0][f];
if(abs(a[mid].w-a[mid+1].w)<=delta)curr=min(curr,s.ans[i][1]+t.ans[1][f]-a[mid].a-a[mid+1].a+a[mid].b+a[mid+1].b);
if(abs(a[mid].w-a[mid+2].w)<=delta)curr=min(curr,s.ans[i][1]+t.ans[2][f]-a[mid].a-a[mid+2].a+a[mid].b+a[mid+2].b);
if(abs(a[mid-1].w-a[mid+1].w)<=delta)curr=min(curr,s.ans[i][2]+t.ans[1][f]-a[mid-1].a-a[mid+1].a+a[mid-1].b+a[mid+1].b);
}
}
}
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++){
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++;
}*/
solve(1,1,n);
ans[qs[i].second]=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;
}*/
