#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) int(x.size())
using ll = long long;
using pii = pair<int, int>;
#define X first
#define Y second
template<typename T> void permute(vector<T> &A, vector<int> &p) {
vector<T> B(SZ(A));
for(int i=0; i<SZ(A); i++)
B[i] = A[p[i]];
A = B;
}
const int MXN = 1e5+5;
int n, q;
vector<int> ord, ordq;
int dsu[MXN], sz[MXN], mnod[MXN], mnev[MXN], val[MXN];
ll ANS;
inline int get(int v) {
return (sz[v]&1) ? min(mnod[v], val[v]) : 0;
}
inline void init(vector<int> &A, vector<int> &B) {
ANS = 0;
for(int i=0; i<n; i++) {
dsu[i] = i;
sz[i] = 1;
mnod[i] = A[i]-B[i];
mnev[i] = 1e9;
val[i] = 1e9;
ANS += get(i);
}
}
int find(int v) { return v==dsu[v] ? v : dsu[v]=find(dsu[v]); }
inline void merge(int u, int v) {
u = find(u);
v = find(v);
assert(u!=v);
ANS -= get(u);
ANS -= get(v);
mnod[u] = min(mnod[u], (sz[u]&1) ? mnev[v] : mnod[v]);
mnev[u] = min(mnev[u], (sz[u]&1) ? mnod[v] : mnev[v]);
val[u] = min(val[u], val[v]);
sz[dsu[v]=u] += sz[v];
ANS += get(u);
}
inline void add(int i, int x) {
i = find(i);
ANS -= get(i);
val[i] = min(val[i], x);
ANS += get(i);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
n = SZ(W), q = SZ(E);
ord.resize(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return W[i]<W[j];
});
permute(W, ord);
permute(A, ord);
permute(B, ord);
ordq.resize(q);
iota(ordq.begin(), ordq.end(), 0);
sort(ordq.begin(), ordq.end(), [&](int i, int j) {
return E[i]<E[j];
});
permute(E, ordq);
vector<pii> v1, v2;
for(int i=0; i+1<n; i++) {
v1.push_back({W[i+1]-W[i], i});
if(i+2<n) v2.push_back({W[i+2]-W[i], i});
}
sort(v1.begin(), v1.end()); reverse(v1.begin(), v1.end());
sort(v2.begin(), v2.end()); reverse(v2.begin(), v2.end());
init(A, B);
vector<ll> ans(q);
ll sumb=0;
for(int i : B) sumb += i;
for(int i=0; i<q; i++) {
while(!v1.empty() && v1.back().X<=E[i]) {
merge(v1.back().Y, v1.back().Y+1);
v1.pop_back();
}
while(!v2.empty() && v2.back().X<=E[i]) {
add(v2.back().Y+1, A[v2.back().Y+1]-B[v2.back().Y+1]);
v2.pop_back();
}
ans[ordq[i]] = sumb + ANS;
}
return ans;
}
