#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;
struct segtree {
vector<long long> tree;
int offset = 1;
segtree(int n) {
while (offset < n) offset <<= 1;
tree.resize(offset << 1);
}
void update(int i, long long x) {
tree[i += offset] = x;
while (i >>= 1) tree[i] = min(tree[i*2], tree[i*2 + 1]);
}
long long query(int v, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[v];
if (qr < l || r < ql) return 1e18;
int mid = l+r >> 1;
return min(query(2*v, l, mid, ql, qr),
query(2*v+1, mid+1, r, ql, qr));
}
long long query(int l, int r) { return query(1, 0, offset - 1, l, r); }
};
long long solve(vector<int> W, vector<int> A,
vector<int> B, int D) {
int n = W.size();
vector<int> ind(n);
iota(all(ind), 0);
sort(all(ind), [&](int i, int j) { return W[i] < W[j]; });
vector<long long> dp(n);
segtree s(n);
dp[0] = A[ind[0]];
long long sum = A[ind[0]];
int j = 0;
s.update(0, -A[ind[0]] + B[ind[0]]);
for (int i = 1; i < n; i++) {
while (W[ind[i]] - W[ind[j]] > D)
j++;
dp[i] = dp[i-1] + A[ind[i]];
if (j < i) {
dp[i] = min(dp[i], sum + s.query(j, i-1) + B[ind[i]]);
}
sum += A[ind[i]];
s.update(i, -sum + dp[i-1] + B[ind[i]]);
}
return dp[n-1];
}
vector<long long> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E
) {
int n = W.size(), q = E.size();
vector<long long> res(q);
for (int i = 0; i < q; i++) {
res[i] = solve(W, A, B, E[i]);
}
return res;
}
