#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define cmax(a, b) a=max(a, b)
#define cmin(a, b) a=min(a, b)
#define fi first
#define se second
vector<pair<int, int>> leftt;
int calc(int d, int l, int r) { int n=r-l+1;
if ((r-l+1)%2==0) return 0;
int ans=min(leftt[l].se, leftt[r].se);
for (int i=l; i<=r; i+=2) cmin(ans, leftt[i].se);
for (int i=l; i<n-1; i++) {
if (leftt[i+1].fi-leftt[i-1].fi<=d) cmin(ans, leftt[i].se);
}
return ans;
}
int n, q, base;
vector<pair<int, int>> a;
vector<int> par, szz, odd, even, best;
int getpar(int x) {
if (x==par[x]) return x;
return par[x]=getpar(par[x]);
}
void merge(int a, int &ans) {
int b=a+1;
a=getpar(a), b=getpar(b);
if (a==b) return;
ans-=(szz[a]%2)*min(best[a], odd[a])+(szz[b]%2)*min(best[b], odd[b]);
if (szz[a]%2) swap(odd[b], even[b]);
cmin(odd[a], odd[b]), cmin(even[a], even[b]), cmin(best[a], best[b]);
szz[a]+=szz[b];
par[b]=a;
ans+=(szz[a]%2)*min(best[a], odd[a]);
}
void add(int a, int val, int &ans) {
a=getpar(a);
ans-=(szz[a]%2)*min(best[a], odd[a]);
cmin(best[a], val);
ans+=(szz[a]%2)*min(best[a], odd[a]);
}
vector<int> calculate_costs(vector<signed> _w, vector<signed> _a, vector<signed> _b, vector<signed> e) { n=sz(_w), q=sz(e);
base=0;
int ans=0;
for (int i=0; i<n; i++) base+=(int)_b[i], _a[i]-=_b[i];
for (int i=0; i<n; i++) a.pb({_w[i], _a[i]}), ans+=_a[i];
sort(all(a));
par.resize(n, 0), szz.resize(n, 1); iota(all(par), 0);
odd.resize(n), even.resize(n, 1e18), best.resize(n, 1e18);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq2;
for (int i=0; i<n-1; i++) pq.push({a[i+1].fi-a[i].fi, i});
for (int i=1; i<n-1; i++) pq2.push({a[i+1].fi-a[i-1].fi, i});
for (int i=0; i<n; i++) odd[i]=a[i].se;
vector<int> answers(q);
vector<pair<int, int>> queries;
for (int i=0; i<q; i++) queries.pb({e[i], i});
sort(all(queries));
for (auto [d, pos]: queries) {
while (!pq.empty() && pq.top().fi<=d) {
merge(pq.top().se, ans);
pq.pop();
}
while (!pq2.empty() && pq2.top().fi<=d) {
add(pq2.top().se, a[pq2.top().se].se, ans);
pq2.pop();
}
answers[pos]=base+ans;
}
return answers;
}
