#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;
struct dsu {
vector<int> par, rank, size;
int odd_comps = 0;
dsu(int n): par(n), rank(n), size(n, 1), odd_comps(n) {
iota(all(par), 0);
}
int find(int u) {
return par[u] == u ? u : par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u != v) {
if (rank[u] < rank[v]) swap(u, v);
par[v] = u;
rank[u] += rank[u] == rank[v];
odd_comps -= size[u] & 1;
odd_comps -= size[v] & 1;
size[u] += size[v];
odd_comps += size[u] & 1;
}
}
};
vector<long long> sub6(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E
) {
int n = W.size(), q = E.size();
vector<int> E_ind(q);
iota(all(E_ind), 0);
sort(all(E_ind), [&](int i, int j) { return E[i] < E[j]; });
vector<int> W_ind(n);
iota(all(W_ind), 0);
sort(all(W_ind), [&](int i, int j) { return W[i] < W[j]; });
vector<pair<int,int>> edges;
for (int i = 0; i < n-1; i++)
edges.emplace_back(W_ind[i+1] - W_ind[i], i);
sort(all(edges));
int ptr = 0;
dsu d(n);
vector<long long> ans(q);
for (int i : E_ind) {
while (ptr < edges.size() && edges[ptr].first <= E[i]) {
d.merge(edges[ptr].second, edges[ptr].second + 1);
ptr++;
}
ans[i] = 2*d.odd_comps;
}
return ans;
}
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
) {
bool subtask6 = true;
for (int x : A) subtask6 &= x == 2;
for (int x : B) subtask6 &= x == 1;
if (subtask6) {
return sub6(W, A, B, 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;
}
