#include"nile.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;
struct Mat{
vector<vector<ll>> d;
Mat(ll v=inf):d(vector<vector<ll>>(3,vector<ll>(3,v))){}
Mat operator*(const Mat& o){
Mat m;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
m.d[i][k]=min(m.d[i][k], d[i][j] + o.d[j][k]);
}
}
}
return m;
}
};
struct T{
int n;
vector<array<int,3>> a;
vector<Mat> t;
T(int _n, vector<array<int,3>> _a){
n=_n-2;
a=_a;a.erase(begin(a),begin(a)+2);
t.resize(4*n);
for(int i=0;i<n;i++)set(i,0);
}
void set(int i,int tp){
Mat m;
m.d[0][1]=a[i][1];
m.d[1][2]=a[i][2];
m.d[2][2]=a[i][1];
if(tp>=1)m.d[2][1]=a[i][2];
if(tp>=2)m.d[2][0]=a[i][2];
set(1, 0, n-1, i, i, m);
}
void set(int x,int l,int r,int ql,int qr, Mat m){
if(l>qr||r<ql)return;
if(ql<=l&&r<=qr){
t[x]=m;
return;
}
int mi=(l+r)/2;
set(2*x,l,mi,ql,qr,m);
set(2*x+1,mi+1,r,ql,qr,m);
t[x]=t[2*x+1]*t[2*x];
}
Mat query(){
if(n==0){
Mat m;
m.d[0][0]=0;
m.d[1][1]=0;
m.d[2][2]=0;
return m;
}
return t[1];
}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
int n=ssize(W),q=ssize(E);
vector<array<int,3>> a(n);
for(int i=0;i<n;i++)a[i]={W[i],A[i],B[i]};
sort(begin(a),end(a));
if(n<=1){
vector<ll> res;
res.insert(begin(res),q,a[0][1]);
return res;
}
vector<array<int,3>> upd;
for(int i=2;i<n;i++)upd.push_back({a[i][0]-a[i-1][0],i,1});
for(int i=2;i<n;i++)upd.push_back({a[i][0]-a[i-2][0],i,2});
sort(begin(upd),end(upd));
T tree(n, a);
vector<int> b(q);iota(begin(b),end(b),0);
sort(begin(b),end(b),[&](int i,int j){return E[i]<E[j];});
int ui=0;
vector<ll> res(q);
for(int ei=0;ei<q;ei++){
int d=E[b[ei]];
while(ui<ssize(upd)&&upd[ui][0]<=d){
auto[delt,i,t]=upd[ui++];
if(t==1){
tree.set(i-2, 1);
continue;
}
ll cost=a[i][2]+a[i-1][2]+a[i-2][1];
ll newc=a[i][2]+a[i-1][1]+a[i-2][2];
if(newc<cost){
tree.set(i-2,2);
}
}
ll ppu,pu,pm;
ppu=a[0][2]+a[1][1];
pu=a[0][1]+a[1][2];
pm=(a[1][0]-a[0][0]<=d)?a[0][2]+a[1][2]:a[0][1]+a[1][1];
Mat mat=tree.query();
ll ret=min({ppu+mat.d[2][0],pu+mat.d[2][1],pm+mat.d[2][2]});
res[b[ei]]=ret;
}
return res;
}
