#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[W_ind[i+1]] - W[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] = n + d.odd_comps;
}
return ans;
}
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);
dp[0] = A[ind[0]];
for (int i = 1; i < n; i++) {
dp[i] = dp[i-1] + A[ind[i]];
long long sum = 0;
for (int j = i-1; j >= 0 && i-j <= 2; j--) {
dp[i] = min(dp[i], (j == 0 ? 0 : dp[j-1]) + B[ind[i]] + B[ind[j]] + sum);
sum += A[ind[j]];
}
}
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;
}
