#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using tl = tuple<ll,ll,ll>;
const ll INF = 1e9 + 7;
#define F first
#define S second
#define sor(x) sort(begin(x), end(x))
#define FOR(i, a, b) for (int i = a; i < b; i++)
// Variables
int n, q, p = 2;
ll ans = 0;
tl id = {INF, INF, INF};
vector<pl> Art, Queries, Dif, Dif2;
vector<tl> Sg;
vi Link, Left, Right;
vl Ans, SavedCosts;
// Combine function
tl f(tl x, tl y) {
return {min(get<0>(x), get<0>(y)), min(get<1>(x), get<1>(y)), min(get<2>(x), get<2>(y))};
}
// Builds segment tree and union find
void build() {
// Segment tree
while (p < n) p *= 2;
Sg.resize(2 * p, id);
Sg[0] = {0, 0, 0};
for (int i = p; i < 2 * p; i++) {
ll val0 = (i % 2) ? INF : Art[i - p].S;
ll val1 = (i % 2) ? Art[i - p].S : INF;
Sg[i] = {val0, val1, INF};
}
for (int i = p - 1; i > 0; i--) {
Sg[i] = f(Sg[2 * i], Sg[2 * i + 1]);
}
// Union-find
Link.resize(n, 0);
Left.resize(n, 0);
Right.resize(n, 0);
SavedCosts.resize(n, 0);
FOR(i, 0, n) {
Link[i] = i;
Left[i] = i;
Right[i] = i;
SavedCosts[i] = Art[i].S;
}
Ans.resize(q, 0);
}
// Point updates
void update(int index, ll value, int lo, int hi, int node) {
if (hi < index || index < lo) return;
if (lo == hi) {
Sg[node] = {get<0>(Sg[node]), get<1>(Sg[node]), value};
return;
}
int mid = (lo + hi) / 2;
update(index, value, lo, mid, 2 * node);
update(index, value, mid + 1, hi, 2 * node + 1);
Sg[node] = f(Sg[2 * node], Sg[2 * node + 1]);
}
// Range minimum query
ll query(int l, int r, int lo, int hi, int node, int mode) {
if (hi < l || r < lo) return INF;
if (l <= lo && hi <= r) {
if (mode == 0) return get<0>(Sg[node]);
if (mode == 1) return get<1>(Sg[node]);
if (mode == 2) return get<2>(Sg[node]);
}
int mid = (lo + hi) / 2;
return min(query(l, r, lo, mid, 2 * node, mode), query(l, r, mid + 1, hi, 2 * node + 1, mode));
}
// Returns cost to process range (ONLY CALL ON REPRESENTATIVES)
ll cost(int u) {
if ((Right[u] - Left[u]) % 2) return 0;
ll a = query(Left[u], Right[u], 0, p - 1, 1, 2);
ll b = query(Left[u], Right[u], 0, p - 1, 1, Left[u] % 2);
return min(a, b);
}
// Find function with path compression
int find(int u) {
return (u == Link[u]) ? u : Link[u] = find(Link[u]);
}
void unite(int u, int v) {
ans -= SavedCosts[u] + SavedCosts[v];
if (Left[v] - Left[v] > Right[u] - Left[u]) swap(u, v);
Link[v] = u;
Left[u] = min(Left[u], Left[v]);
Right[u] = max(Right[u], Right[v]);
SavedCosts[u] = cost(u);
ans += SavedCosts[u];
}
// Reads input
void read(vi W, vi A, vi B, vi E) {
n = W.size();
q = E.size();
Art.resize(n, {2 * INF, INF});
FOR(i, 0, n) {
ll w = (ll)W[i], a = (ll)A[i], b = (ll)B[i];
Art.push_back({w, a - b});
ans += a;
}
sor(Art);
FOR(i, 0, n - 1) {
Dif.push_back({Art[i + 1].F - Art[i].F, i});
if (0 < i) Dif2.push_back({Art[i + 1].F - Art[i - 1].F, i});
}
sor(Dif);
sor(Dif2);
FOR(i, 0, q) {
ll e = (ll)E[i];
Queries.push_back({e, i});
}
sor(Queries);
}
// Main function
vl calculate_costs(vi W, vi A, vi B, vi E) {
read(W, A, B, E);
build();
//for (auto a : Art) cout << "(" << a.F << "," << a.S << ") "; cout << endl;
//for (auto s : Sg) cout << "(" << get<0>(s) << "," << get<1>(s) << "," << get<2>(s) << ") "; cout << endl;
//cout << query(0, 0, 0, p - 1, 1, 0) << " " << query(0, 0, 0, p - 1, 1, 1) << " " << query(0, 0, 0, p - 1, 1, 2) << endl;
int r1 = 0, r2 = 0;
FOR(i, 0, q) {
ll d = Queries[i].F;
while (r2 < n - 2 && Dif2[r2].F <= d) {
int u = Dif2[r2].S;
update(u, Art[u].S, 0, p - 1, 1);
r2++;
u = find(u);
ans -= SavedCosts[u];
SavedCosts[u] = cost(u);
ans += SavedCosts[u];
}
while (r1 < n - 1 && Dif[r1].F <= d) {
int u = Dif[r1].S;
unite(find(u), find(u + 1));
r1++;
}
//FOR(s, 0, n) cout << find(s) << " "; cout << endl;
//FOR(s, 0, n) cout << "(" << Left[s] << "," << Right[s] << ") "; cout << endl;
//FOR(s, 0, n) cout << cost(find(s)) << " "; cout << endl;
//cout << r1 << " " << r2 << endl;
//for (auto s : Sg) cout << "(" << get<0>(s) << "," << get<1>(s) << "," << get<2>(s) << ") "; cout << endl;
//cout << endl;
Ans[Queries[i].S] = ans;
}
return Ans;
}
