#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
const int N = 2e5 + 5;
int par[N], mn[N], sum[N], len[N];
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
par[y] = x;
sum[x] += sum[y];
len[x] += len[y];
mn[x] = min(mn[x], mn[y]);
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = (int)w.size(), q = (int)e.size();
vector<pii> at, qt;
vector<ll> ans(q);
for (int i = 0; i < n; i++) at.push_back({w[i], i});
for (int i = 0; i < q; i++) qt.push_back({e[i], i});
sort(at.begin(), at.end());
sort(qt.begin(), qt.end());
ll res = 0;
for (int i = 0; i < n; i++) {
par[i] = i, len[i] = 1;
mn[i] = a[at[i].se] - b[at[i].se];
sum[i] = b[at[i].se];
res += a[at[i].se];
}
priority_queue<pii> pq;
for (int i = 0; i < n - 1; i++) {
pq.push({-(at[i + 1].fi - at[i].fi), i});
}
for (int i = 0; i < q; i++) {
while (!pq.empty() and -pq.top().fi <= qt[i].fi) {
int x = pq.top().se, y = x + 1;
pq.pop();
x = find(x), y = find(y);
res -= sum[x] + sum[y];
if (len[x] % 2) res -= mn[x];
if (len[y] % 2) res -= mn[y];
merge(x, y);
x = find(x);
res += sum[x];
if (len[x] % 2) res += mn[x];
}
ans[qt[i].se] = res;
}
return ans;
}
