#include <bits/stdc++.h>
using namespace std;
#define int long long
struct _obj {
int a, b, w;
};
struct rg {
int l , r, sum, mn0, mn1, ans;
};
struct _lnk {
int df;
int idx; //with idx+1
};
bool comp1(_obj a, _obj b) {
return a.w < b.w;
}
bool comp2(_lnk a, _lnk b) {
return a.df < b.df;
}
int res = 0;
const int N = 1e5+5;
const int INF = 1e18;
rg Z[N];
set<int> lfs,rgs;
void join(int i) {
rg R; R.l = Z[i].l; R.r = Z[i+1].r;
R.sum = Z[i].sum + Z[i+1].sum; res -= Z[i].ans; res -= Z[i+1].ans;
if ((Z[i].r - Z[i].l + 1)&1) swap(Z[i+1].mn0, Z[i+1].mn1);
R.mn0 = min(Z[i].mn0, Z[i+1].mn0); R.mn1 = min(Z[i].mn1, Z[i+1].mn1);
if ((R.r - R.l)&1) R.ans = R.sum; else R.ans = R.sum + R.mn0;
res += R.ans;
rgs.erase(i); lfs.erase(i+1);
Z[R.l] = R; Z[R.r] = R;
}
void upd(int i, int nv) {
int r = *rgs.lower_bound(i);
rg R = Z[r]; res -= R.ans;
R.mn0 = min(R.mn0, nv); R.mn1 = min(R.mn1, nv);
if ((R.r - R.l)&1) R.ans = R.sum; else R.ans = R.sum + R.mn0;
res += R.ans;
Z[R.l] = R; Z[R.r] = R;
}
vector<long long> calculate_costs(vector<signed> W, vector<signed> A, vector<signed> B, vector<signed> E) {
int n = W.size();
vector<_obj> p(n); for (int i=0; i<n; i++) p[i].a = A[i], p[i].b = B[i], p[i].w = W[i];
sort(p.begin(), p.end(), comp1);
vector<_lnk> evs;
for (int i=0; i<n-1; i++) {
_lnk t; t.df = p[i+1].w - p[i].w; t. idx = i;
evs.push_back(t);
}
sort(evs.begin(), evs.end(), comp2);
vector<pair<int,int>> qs;
vector<int> ans((int)E.size());
for (int i=0; i<E.size(); i++) qs.push_back({E[i], i});
sort(qs.begin(), qs.end());
for (int i=0; i<n; i++) {
lfs.insert(i); rgs.insert(i);
Z[i].l = i; Z[i].r = i; Z[i].sum = p[i].b;
Z[i].mn0 = p[i].a-p[i].b; Z[i].ans = p[i].a; Z[i].mn1 = INF;
res += p[i].a;
}
vector<_lnk> ps2;
for (int i=1; i<n-1; i++) {
_lnk t; t.df = p[i+1].w - p[i-1].w; t.idx = i;
ps2.push_back(t);
}
sort(ps2.begin(), ps2.end(), comp2);
int j=0; int t = 0;
for (auto [d, idx]: qs) {
while (j<evs.size() && evs[j].df <= d) {
join(evs[j].idx); j++;
}
while (t<ps2.size() && ps2[t].df <= d) {
int i = ps2[t].idx;
upd(i, p[i].a - p[i].b);
t++;
}
ans[idx] = res;
}
return ans;
}
