#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
ll dist_d_idx(ll i, vector<ll> v, ll d){
auto it = lower_bound(v.begin(), v.end(), v[i]-d);
return it - v.begin();
}
void seg_update(ll i, ll p, pll val, vector<pll> &seg){
i += p;
seg[i] = val;
for(i /= 2; i > 0; i /= 2) seg[i] = min(seg[2*i], seg[2*i+1]);
}
void update(ll a, ll b, ll p, vector<pll> &seg, vector<ll> &match, vector<ll> &c, ll &ans){
match[a] = b; match[b] = a;
seg_update(a, p, {c[b], a}, seg); seg_update(b, p, {c[a], b}, seg);
ans += c[a] + c[b];
}
pll min_query(ll a, ll b, ll p, vector<pll> &seg){
a += p; b += p;
pll mi = {inf, inf};
while(a <= b){
if(a % 2 == 1) mi = min(mi, seg[a++]);
if(b % 2 == 0) mi = min(mi, seg[b--]);
a /= 2; b /= 2;
}
return mi;
}
void swap_with_min_matched(ll i, ll d, ll p, vector<ll> &match, vector<pll> &seg, vector<ll> &c, vector<ll> &w, ll &ans){
ll range_start = dist_d_idx(i, w, d);
auto[min_val, min_idx] = min_query(range_start, i-1, p, seg);
if(min_val >= c[i]) return;
if(min_val == 0){
update(min_idx, i, p, seg, match, c, ans);
return;
}
ans -= min_val; ans -= c[min_idx];
ll prev_match = match[min_idx];
match[prev_match] = prev_match;
seg_update(prev_match, p, {0, prev_match}, seg);
update(min_idx, i, p, seg, match, c, ans);
}
ll max_c_matching(ll n, vector<ll> w, vector<ll> c, ll d){
ll p = 1, ans = 0;
while(p <= n) p *= 2;
vector<pll> seg(2*p);
vector<ll> match(n);
for(ll i = 0; i < n; i++){
if(i < n-1){
if(w[i+1] - w[i] <= d) {update(i, i+1, p, seg, match, c, ans); i++; continue;}
}
swap_with_min_matched(i, d, p, match, seg, c, w, ans);
}
return ans;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
ll n = W.size(), q = E.size(), sum_a = 0;
vector<ll> w(n), a(n), b(n), c(n), e(q);
for(ll i = 0; i < n; i++) w[i] = W[i], a[i] = A[i], b[i] = B[i], c[i] = a[i] - b[i], sum_a += a[i];
for(ll i = 0; i < q; i++) e[i] = E[i];
vector<pll> v(n);
for(ll i = 0; i < n; i++) v[i] = {w[i], c[i]};
sort(v.begin(), v.end());
for(ll i = 0; i < n; i++) w[i] = v[i].first, c[i] = v[i].second;
vector<ll> ans(q);
for(ll i = 0; i < q; i++) ans[i] = sum_a - max_c_matching(n, w, c, e[i]);
return ans;
}
