#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Block {
ll sum, ans;
int odd, even, len, T[2];
};
struct Node {
int w, a, b;
};
struct Query {
int d, id;
};
const int MAXN = 100000 + 5;
const int INF = 0x3f3f3f3f;
Block c[MAXN];
Node a[MAXN];
Query q[MAXN], p[MAXN], r[MAXN];
int n, h_[MAXN], t_[MAXN];
bool cmpQ(const Query &x, const Query &y) { return x.d < y.d; }
bool cmpNode(const Node &x, const Node &y) { return x.w < y.w; }
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int Q = (int)E.size();
n = (int)W.size();
ll ans = 0;
for (int i = 0; i < n; i++) {
a[i + 1] = {W[i], A[i], B[i]};
ans += A[i];
}
for (int i = 0; i < Q; i++) {
q[i + 1] = {E[i], i + 1};
}
sort(a + 1, a + n + 1, cmpNode);
sort(q + 1, q + Q + 1, cmpQ);
set<int> se;
for (int i = 1; i <= n; i++) {
t_[i] = h_[i] = i;
c[i].sum = a[i].b;
c[i].ans = a[i].a;
c[i].odd = a[i].a - a[i].b;
c[i].even = INF;
c[i].len = 1;
c[i].T[0] = c[i].T[1] = INF;
se.insert(i);
}
int ct = 0;
for (int i = 2; i < n; i++) {
p[++ct] = {a[i + 1].w - a[i - 1].w, i};
}
for (int i = 1; i < n; i++) {
r[i] = {a[i + 1].w - a[i].w, i};
}
sort(p + 1, p + ct + 1, cmpQ);
sort(r + 1, r + n, cmpQ);
vector<long long> R(Q, 0);
int p1 = 1, p2 = 1;
for (int i = 1; i <= Q; i++) {
int D = q[i].d;
while (p1 < n && r[p1].d <= D) {
int u = r[p1].id;
int b1 = h_[u];
int b2 = u + 1;
c[b1].sum += c[b2].sum;
c[b1].T[0] = min(c[b1].T[0], c[b2].T[0]);
c[b1].T[1] = min(c[b1].T[1], c[b2].T[1]);
ans -= c[b1].ans + c[b2].ans;
if ((c[b1].len + c[b2].len) % 2 == 0) {
c[b1].ans = c[b1].sum;
ans += c[b1].sum;
} else {
ll res = c[b1].ans + c[b2].ans;
if (c[b1].len % 2 == 1) {
res = min(res, c[b1].sum + c[b2].even);
} else {
res = min(res, c[b1].sum + c[b1].odd);
}
res = min(res, c[b1].sum + c[b1].T[!(b1 % 2)]);
c[b1].ans = res;
ans += res;
}
if (c[b1].len % 2 == 1) {
swap(c[b2].odd, c[b2].even);
}
c[b1].odd = min(c[b1].odd, c[b2].odd);
c[b1].even = min(c[b1].even, c[b2].even);
c[b1].len += c[b2].len;
h_[t_[b2]] = b1;
t_[b1] = t_[b2];
se.erase(b2);
p1++;
}
while (p2 <= ct && p[p2].d <= D) {
int u = p[p2].id;
auto it = se.upper_bound(u);
--it;
int head = *it;
c[head].T[u % 2] = min(c[head].T[u % 2], a[u].a - a[u].b);
ans -= c[head].ans;
if (c[head].len % 2 == 1) {
c[head].ans = min(c[head].ans, c[head].sum + c[head].T[!(head % 2)]);
}
ans += c[head].ans;
p2++;
}
R[q[i].id - 1] = ans;
}
return R;
}
