#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int INF = 1e9;
vector<ll>calculate_costs(vector<int>W, vector<int>A, vector<int>B, vector<int>E){
int n = W.size(), q = E.size();
if(n == 1){
return vector<ll>(q, ll(A[0]));
}
if(q <= 5 && n <= 2000 && *max_element(W.begin(), W.end()) == 1){
ll ans = accumulate(B.begin(), B.end(), 0LL);
if(n & 1){
int d = INF;
for(int i = 0; i < n; i++){
minimize(d, A[i] - B[i]);
}
ans += d;
}
return vector<ll>(q, ans);
}
vector<int>p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j){
return W[i] < W[j];
});
vector<int>pd(n - 1);
iota(pd.begin(), pd.end(), 0);
sort(pd.begin(), pd.end(), [&] (int i, int j){
return W[p[i + 1]] - W[p[i]] < W[p[j + 1]] - W[p[j]];
});
vector<int>pst(n - 2);
iota(pst.begin(), pst.end(), 1);
sort(pst.begin(), pst.end(), [&] (int i, int j){
return W[p[i + 1]] - W[p[i - 1]] < W[p[j + 1]] - W[p[j - 1]];
});
vector<vector<int>>st(4, vector<int>(n << 2, INF));
function<void(int, int, int, int, int, int)>update;
update = [&] (int type, int id, int l, int r, int p, int x){
if(l == r){
st[type][id] = x;
return;
}
int m = (l + r) >> 1;
if(m < p){
update(type, id << 1 | 1, m + 1, r, p, x);
}
else{
update(type, id << 1, l, m, p, x);
}
st[type][id] = min(st[type][id << 1], st[type][id << 1 | 1]);
};
function<int(int, int, int, int, int, int)>get;
get = [&] (int type, int id, int l, int r, int u, int v){
if(l > v || r < u){
return INF;
}
if(u <= l && v >= r){
return st[type][id];
}
int m = (l + r) >> 1;
return min(get(type, id << 1, l, m, u, v), get(type, id << 1 | 1, m + 1, r, u, v));
};
for(int i = 0; i < n; i++){
update(i & 1, 1, 0, n - 1, i, A[p[i]] - B[p[i]]);
}
auto get_range = [&] (int l, int r){
return ((r - l) & 1) ? 0 : min(get(l & 1, 1, 0, n - 1, l, r), get(((l & 1) ^ 1) | 2, 1, 0, n - 1, l, r));
};
ll cur = accumulate(A.begin(), A.end(), 0LL);
vector<int>lab(n), l(n), r(n);
for(int i = 0; i < n; i++){
lab[i] = l[i] = r[i] = i;
}
auto find_set = [&] (int N){
while(N != lab[N]){
N = lab[N] = lab[lab[N]];
}
return N;
};
auto merge = [&] (int u, int v){
cur -= get_range(l[u = find_set(u)], r[u]) + get_range(l[v = find_set(v)], r[v]);
minimize(l[lab[v] = u], l[v]);
maximize(r[u], r[v]);
cur += get_range(l[u], r[u]);
};
vector<int>pq(q);
iota(pq.begin(), pq.end(), 0);
sort(pq.begin(), pq.end(), [&] (int i, int j){
return E[i] < E[j];
});
vector<ll>ans(q);
int ipd = 0, ist = 0;
for(int& iq : pq){
while(ist + 2 < n && W[p[pst[ist] + 1]] - W[p[pst[ist] - 1]] <= E[iq]){
int i = find_set(pst[ist]);
cur -= get_range(l[i], r[i]);
update((pst[ist] & 1) | 2, 1, 0, n - 1, pst[ist], A[p[pst[ist]]] - B[p[pst[ist]]]);
cur += get_range(l[i], r[i]);
ist++;
}
while(ipd + 1 < n && W[p[pd[ipd] + 1]] - W[p[pd[ipd]]] <= E[iq]){
merge(pd[ipd], pd[ipd] + 1);
ipd++;
}
ans[iq] = cur;
}
return ans;
}
