#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=1e5+5, inf=1e18;
struct info
{
ll w, a, b;
info(ll w=0, ll a=0, ll b=0): w(w), a(a), b(b){}
bool operator< (const info &o) const {return w<o.w;}
} d[nx];
struct segtree
{
struct mat
{
ll a[3][3];
mat(int idx=-1)
{
for (int i=0; i<3; i++) for (int j=0; j<3; j++) a[i][j]=inf;
if (idx!=-1)
{
a[0][0]=a[1][2]=d[idx].a;
a[0][1]=d[idx].b;
}
}
} node[4*nx];
mat merge(mat &lhs, mat &rhs)
{
mat res;
for (int i=0; i<3; i++) for (int j=0; j<3; j++) for (int k=0; k<3; k++) res.a[i][j]=min(res.a[i][j], lhs.a[i][k]+rhs.a[k][j]);
return res;
}
void build(int l, int r, int i)
{
if (l==r) return node[i]=mat(l), void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
node[i]=merge(node[2*i], node[2*i+1]);
//cout<<"after "<<l<<' '<<r<<' '<<node[i].a[0][0]<<'\n';
}
void update(int l, int r, int i, int idx, int t)
{
if (idx<l||r<idx) return;
if (l==r)
{
//cout<<"update "<<idx<<' '<<t<<'\n';
if (t==1) node[i].a[1][0]=d[l].b;
else node[i].a[2][0]=d[l].b;
return;
}
int md=(l+r)/2;
update(l, md, 2*i, idx, t);
update(md+1, r, 2*i+1, idx, t);
node[i]=merge(node[2*i], node[2*i+1]);
}
} s;
ll n, dp[nx];
vector<ll> res;
vector<pair<ll, ll>> qrs;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq1, pq2;
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
n=W.size();
for (int i=1; i<=n; i++) d[i]=info(W[i-1], A[i-1], B[i-1]);
sort(d+1, d+n+1);
for (int i=2; i<=n; i++) pq1.push({d[i].w-d[i-1].w, i});
for (int i=3; i<=n; i++) pq2.push({d[i].w-d[i-2].w, i});
res.resize(E.size());
for (int i=0; i<E.size(); i++) qrs.push_back({E[i], i});
sort(qrs.begin(), qrs.end());
s.build(1, n, 1);
//cout<<"debug "<<s.node[1].a[0][0]<<'\n';
for (auto [x, idx]:qrs)
{
while (!pq1.empty()&&pq1.top().first<=x) s.update(1, n, 1, pq1.top().second, 1), pq1.pop();
while (!pq2.empty()&&pq2.top().first<=x) s.update(1, n, 1, pq2.top().second, 2), pq2.pop();
//cout<<"answer "<<idx<<'\n';
res[idx]=s.node[1].a[0][0];
}
return res;
}
