#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
struct DSU {
int n;
vl par, size;
vector<array<ll, 5>> data; // v0, v1, sum, save, skip
ll saved = 0;
DSU(int sz) {
n = sz;
par = vl(n);
size = vl(n, 1);
data = vector<array<ll, 5>>(n);
for (int i = 0; i < n; i++) par[i] = i;
}
int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]); }
void join(int l, int r) {
l = find(l), r = find(r);
if (l == r) return;
ll v0 = min(data[l][0], data[r][0]);
ll v1 = min(data[l][1], data[r][1]);
ll sum = data[l][2]+data[r][2];
saved -= data[l][3]+data[r][3];
if (size[l]&1) {
v0 = min(data[l][0], data[r][1]);
v1 = min(data[l][1], data[r][0]);
}
ll cont = sum;
ll skip = min(data[l][4], data[r][4]);
if ((size[l]+size[r])%2) cont = max(sum-v0, sum-min(sum, skip));
if (size[l] < size[r]) swap(l, r);
saved += cont;
data[l] = {v0, v1, sum, cont, skip};
size[l] += size[r];
par[r] = l;
}
void addskip(int l, ll skip) {
l = find(l);
data[l][4] = max(data[l][4], skip);
saved -= data[l][3];
data[l][3] = max(data[l][3], data[l][2]-min(data[l][2], skip));
saved += data[l][3];
}
};
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
int n = W.size(), q = E.size();
vector<pair<int, int>> wid(n);
ll base = accumulate(A.begin(), A.end(), 0ll);
for (int i = 0; i < n; i++) wid[i] = {W[i], i};
sort(wid.begin(), wid.end());
vector<array<int, 3>> wmrg(n-1);
vector<array<int, 3>> wmrg2(n-2);
for (int i = 0; i+1 < n; i++) {
wmrg[i] = {abs(wid[i].first-wid[i+1].first), i, i+1};
if (i+2 < n) wmrg2[i] = {abs(wid[i].first-wid[i+1].first), i, i+2};
}
sort(wmrg.rbegin(), wmrg.rend());
vector<pair<int, int>> qs(q);
for (int i = 0; i < q; i++) qs[i] = {E[i], i};
sort(qs.begin(), qs.end());
vl ans(q);
DSU dsu(n);
for (int i = 0; i < n; i++) {
int id = wid[i].second;
dsu.data[i] = {A[id]-B[id], (ll)1e18, A[id]-B[id], 0, (ll)1e18};
}
for (int qq = 0; qq < q; qq++) {
auto [d, id] = qs[qq];
while (wmrg.size() && wmrg.back()[0] <= d) {
auto ar = wmrg.back();
wmrg.pop_back();
int l = ar[1], r = ar[2];
dsu.join(l, r);
}
while (wmrg2.size() && wmrg2.back()[0] <= d) {
auto ar = wmrg2.back();
wmrg2.pop_back();
int l = ar[1];
dsu.addskip(l, A[wid[l+1].second]-B[wid[l+1].second]);
}
ans[id] = base-dsu.saved;
}
return ans;
}
