#include<bits/stdc++.h>
using namespace std;
long long ans;
vector<int> DSU, cnt, oddMin, evenMin, avaMin;
int fnd(int a)
{
if (a == DSU[a])
return a;
else
return DSU[a] = fnd(DSU[a]);
}
void uni(int a)
{
int b = a + 1;
int x = fnd(a), y = fnd(b);
if (x != y)
{
if (cnt[x] & 1)
ans -= min(oddMin[x], avaMin[x]);
if (cnt[y] & 1)
ans -= min(oddMin[y], avaMin[y]);
DSU[y] = x;
if (cnt[x] & 1)
{
oddMin[x] = min(oddMin[x], evenMin[y]);
evenMin[x] = min(evenMin[x], oddMin[y]);
}
else
{
oddMin[x] = min(oddMin[x], oddMin[y]);
evenMin[x] = min(evenMin[x], evenMin[y]);
}
cnt[x] += cnt[y];
avaMin[x] = min(avaMin[x], avaMin[y]);
if (cnt[x] & 1)
ans += min(oddMin[x], avaMin[x]);
}
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
int N = W.size();
ans = 0;
vector<pair<int, int>> art;
for (int i = 0; i < N; i++)
{
art.push_back(make_pair(W[i], A[i] - B[i]));
ans += A[i];
}
sort(art.begin(), art.end());
DSU = cnt = oddMin = evenMin = avaMin = vector<int>(N);
for (int i = 0; i < N; i++)
{
DSU[i] = i;
cnt[i] = 1;
oddMin[i] = art[i].second;
evenMin[i] = avaMin[i] = INT_MAX;
}
vector<pair<int, int>> diff;
for (int i = 0; i + 1 < N; i++)
diff.push_back(make_pair(art[i + 1].first - art[i].first, i));
sort(diff.begin(), diff.end(), greater<>());
vector<pair<int, int>> margin;
for (int i = 1; i + 1 < N; i++)
margin.push_back(make_pair(art[i + 1].first - art[i - 1].first, i));
sort(margin.begin(), margin.end(), greater<>());
int Q = E.size();
vector<pair<int, int>> queries;
for (int i = 0; i < Q; i++)
queries.push_back(make_pair(E[i], i));
sort(queries.begin(), queries.end());
vector<long long> R(Q);
for (auto query : queries)
{
int D = query.first, queryIndex = query.second;
while (!diff.empty() && diff.back().first <= D)
uni(diff.back().second), diff.pop_back();
while (!margin.empty() && margin.back().first <= D)
{
int target = margin.back().second;
margin.pop_back();
int root = fnd(target);
if (cnt[root] & 1)
ans -= min(oddMin[root], avaMin[root]);
avaMin[root] = min(avaMin[root], art[target].second);
if (cnt[root] & 1)
ans += min(oddMin[root], avaMin[root]);
}
R[queryIndex] = ans;
}
return R;
}
