#include "nile.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const ll maxn = 1e5 + 100 , inf = 1e18 , mod = 998244353;
ll dp[maxn] ;int d;
vector <int> up[maxn] , up2[maxn] ;
vector <pii> vec , que;
vector <ll> ans ;
struct node{
ll a[2][2][2][2] ;
node(){
rep(a0,0,1)rep(a1,0,1)rep(a2,0,1)rep(a3,0,1)a[a0][a1][a2][a3] = 0;
}
};
inline void mx(ll &x , ll y){
x = max(x,y) ;
}
node seg[4*maxn] ;
void upd(int x,int p = 1 , int l = 0 , int r= sz(vec)-1){
int mid = (l+r)/2 , pl=p<<1 , pr=p<<1|1;
if(x > r || x < l)return ;
if(l == r){
rep(i,0,1)rep(j,0,1)rep(k,0,1)rep(z,0,1)seg[p].a[i][j][k][z] = -inf ;
seg[p].a[0][0][0][1]= 0 ;
seg[p].a[1][0][0][0]= 0 ;
seg[p].a[0][0][0][0]= 0 ;
return;
}
upd(x,pl,l,mid);upd(x,pr,mid+1,r);
rep(i1,0,1){
rep(j1,0,1){
rep(i2,0,1){
rep(j2,0,1){
seg[p].a[i1][j1][i2][j2] = max(0ll ,seg[pl].a[i1][j1][0][0] + seg[pr].a[0][0][i2][j2]) ;
if(vec[mid+1].F-vec[mid].F <= d){
ll w = vec[mid].S + vec[mid+1].S;
// if(l==0 && r==2 && i1+j2+j1+i2==0)cout <<vec[mid].S << " " << vec[mid+1].S <<"<--\n";
mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[1][0][i2][j2] + w);
mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[1][0][i2][j2] + w);
}
if(mid+1 != r && vec[mid+2].F-vec[mid].F <= d){
ll w = vec[mid].S + vec[mid+2].S;
mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[0][1][i2][j2] + w);
mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][0][1] + seg[pr].a[0][1][i2][j2] + w);
}
if(l!=mid && vec[mid+1].F-vec[mid-1].F <= d){
ll w = vec[mid-1].S + vec[mid+1].S;
// if(l==0 && r==4 && i1+j2+j1+i2==0)cout <<seg[pl].a[i1][j1][1][0] << " " << seg[pr].a[1][0][i2][j2] <<"<--\n";
mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][1][0] + seg[pr].a[1][0][i2][j2] + w);
mx(seg[p].a[i1][j1][i2][j2],seg[pl].a[i1][j1][1][0] + seg[pr].a[1][0][i2][j2] + w);
}
}
}
}
}
if(r-l+1==2){
rep(i1,0,1){
rep(j1,0,1){
rep(i2,0,1){
rep(j2,0,1){
if(i1+i2==2 || j2+j1==2)seg[p].a[i1][j1][i2][j2] = -inf ;
}}}}
}
if(r-l+1==3){
rep(i1,0,1){
rep(j1,0,1){
rep(i2,0,1){
rep(j2,0,1){
if(j1+i2==2)seg[p].a[i1][j1][i2][j2] = -inf ;
}}}}
}
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,std::vector<int> B, std::vector<int> E) {
int n = sz(W) ;
ll sm =0 ;
rep(i , 0 ,n-1){
vec.pb({W[i] , A[i]-B[i]}) ;
sm += A[i];
}
rep(i , 0 ,sz(E)-1){
que.pb({E[i] , i}) ;
ans.pb(0);
}
sort(all(vec));
sort(all(que));
rep(i , 0 , n-2){
int x =lower_bound(all(que) , (pii){vec[i+1].F-vec[i].F , -1}) - que.begin() ;
up[x].pb(i);
if(i!=n-2){
x =lower_bound(all(que) , (pii){vec[i+2].F-vec[i].F ,-1}) - que.begin();
up2[x].pb(i);
}
}
d = que[0].F ;
rep(i , 0 ,n-1)upd(i) ;
// rep(i,0,1)rep(j,0,1)rep(k,0,1)rep(z,0,1)cout << seg[2].a[i][j][k][z] ;
// cout << '\n' ;
rep(i , 0 ,sz(que)-1){
ll mx = seg[1].a[0][0][0][0] ;
// cout << d << " " << sm << " " << mx << "\n";
ans[que[i].S] = sm - mx ;
if(i == sz(que)-1)break ;
d = que[i+1].F ;
for(int x : up[i+1])upd(x);
for(int x : up2[i+1])upd(x);
}
return ans;
}
