#include "nile.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
ll find(vector<ll> &p, ll x) {return p[x] == x ? x : find(p, p[x]);}
void unite(vector<ll> &p, vector<ll> &s, vector<ll> &pt, vector<vector<ll>> &d1m, vector<vector<ll>> &d2m, ll x, ll y) {
ll x_root = find(p,x);
ll y_root = find(p,y);
if(x_root == y_root) return;
pt[max(x_root, y_root)] = pt[min(x_root, y_root)];
if(s[x_root] < s[y_root]) swap(x_root, y_root);
s[x_root] += s[y_root];
p[y_root] = x_root;
d1m[x_root] = {min(d1m[x_root][0], d1m[y_root][0]), min(d1m[x_root][1], d1m[y_root][1])};
d2m[x_root] = {min(d2m[x_root][0], d2m[y_root][0]), min(d2m[x_root][1], d2m[y_root][1])};
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
ll q = E.size();
ll n = W.size();
ll sum = 0;
for(ll i=0; i<n; i++) sum += A[i];
std::vector<long long> R(q, 0);
vector<pair<ll,ll>> ws(n);
for(ll i=0; i<n; i++) ws[i] = make_pair(W[i], i);
sort(ws.begin(), ws.end());
vector<ll> w(n), a(n), b(n);
for(ll i=0; i<n; i++) {
w[i] = ws[i].F;
a[i] = A[ws[i].S];
b[i] = B[ws[i].S];
}
vector<pair<ll,ll>> d1(n-1);
vector<pair<ll,ll>> d2(n-2);
for(ll i=0; i<n-1; i++) {
d1[i] = make_pair(w[i+1] - w[i], i);
if(i < n-2) d2[i] = make_pair(w[i+2] - w[i], i);
}
sort(d1.begin(), d1.end());
sort(d2.begin(), d2.end());
vector<ll> parents(n);
vector<ll> parity(n);
vector<vector<ll>> d1m(n, {LLONG_MAX, LLONG_MAX}), d2m(n, {LLONG_MAX, LLONG_MAX});
vector<ll> scores(n);
vector<ll> sizes(n, 1);
iota(parents.begin(), parents.end(),0);
for(ll i=0; i<n; i++) {parity[i] = i %2; d1m[i][i % 2] = a[i]-b[i]; scores[i] = a[i]-b[i];}
vector<pair<ll,ll>> e(q);
for(ll i=0; i<q; i++) e[i] = make_pair(E[i], i);
sort(e.begin(), e.end());
ll d1r=0, d2r = 0;
for(ll i=0; i<q; i++) {
while(d2r < n-2 && d2[d2r].F <= e[i].F) {
ll d2i = d2[d2r].S + 1;
ll d2root = find(parents, d2i);
d2m[d2root][d2i % 2] = min(d2m[d2root][d2i % 2], a[d2i] - b[d2i]);
ll nscore = sizes[d2root] % 2 == 0 ? 0 : min(d1m[d2root][parity[d2root]], d2m[d2root][1-parity[d2root]]);
sum += (nscore - scores[d2root]);
scores[d2root] = nscore;
d2r++;
}
while(d1r < n-1 && d1[d1r].F <= e[i].F) {
ll d1r1 = find(parents, d1[d1r].S), d1r2 = find(parents, d1[d1r].S+1);
unite(parents, sizes, parity, d1m, d2m, d1[d1r].S, d1[d1r].S+1);
ll d1root = find(parents, d1r1);
ll nscore = sizes[d1root] % 2 == 0 ? 0 : min(d1m[d1root][parity[d1root]], d2m[d1root][1-parity[d1root]]);
sum += (nscore - scores[d1r1] - scores[d1r2]);
scores[d1root] = nscore;
d1r++;
}
R[e[i].S] = sum;
}
return R;
}
