//#include "nile.h"
#include "bits/stdc++.h"
using namespace std;
long long sz[100005] , par[100005] , mn[100005] , sumb[100005];
long long sum;
int P(int node)
{
if(node == par[node])
return par[node];
return par[node] = P(par[node]);
}
void mrg(int a , int b)
{
int u = P(a) , v = P(b);
if(u == v)
return;
if(sz[u] < sz[v])
swap(u , v);
if(sz[u] % 2)
sum -= sumb[u] + mn[u];
else
sum -= sumb[u];
if(sz[v] % 2)
sum -= sumb[v] + mn[v];
else
sum -= sumb[v];
sumb[u] += sumb[v];
mn[u] = min(mn[u] , mn[v]);
sz[u] += sz[v];
par[v] = u;
sum += sumb[u];
if(sz[u] % 2)
sum += mn[u];
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> A , std::vector<int> B, std::vector<int> E) {
if(E.size() <= 5)
{
long long n = A.size() , q = E.size() , sum = accumulate(A.begin() , A.end() , 0LL);
vector<int> dif(n + 5);
vector<pair<int , int>> W;
for(int i = 0 ; i < n ; i++)
W.push_back({w[i] , i});
sort(W.begin() , W.end());
sort(w.begin() , w.end());
for(int i = 1 ; i <= n ; i++)
dif[i] = A[W[i - 1].second] - B[W[i - 1].second];
vector<long long> ans(q);
vector<pair<int , int>> e;
for(int i = 0 ; i < q ; i++)
e.push_back({E[i] , i});
sort(e.begin() , e.end());
multiset<long long> mx;
vector<long long> dp(n + 5 , 0);
while(q--)
{
long long d = e.back().first , ine = e.back().second;
e.pop_back();
vector<long long> dp(n + 5 , 0);
multiset<long long> mx;
int l = 1;
for(int i = 1 ; i <= n ; i++)
{
if(i > 1)
mx.insert(dp[i - 2] + dif[i - 1]);
while(l < i && w[i - 1] - w[l - 1] > d)
{
mx.erase(mx.find(dp[l - 1] + dif[l]));
l++;
}
dp[i] = dp[i - 1];
if(mx.size())
dp[i] = max(dp[i] , dif[i] + *mx.rbegin());
}
ans[ine] = sum - dp[n];
}
return ans;
}
long long n = A.size() , q = E.size();
sum = accumulate(A.begin() , A.end() , 0LL);
vector<int> dif(n + 5) , a(n + 5) , b(n + 5);
vector<pair<int , int>> W;
for(int i = 0 ; i < n ; i++)
W.push_back({w[i] , i});
sort(W.begin() , W.end());
sort(w.begin() , w.end());
for(int i = 1 ; i <= n ; i++)
a[i] = A[W[i - 1].second] , b[i] = B[W[i - 1].second];
vector<array<int , 3>> ed;
for(int i = 1 ; i < n ; i++)
ed.push_back({w[i] - w[i - 1] , i , i + 1});
sort(ed.begin() , ed.end());
vector<long long> ans(q);
vector<pair<int , int>> e;
for(int i = 0 ; i < q ; i++)
e.push_back({E[i] , i});
for(int i = 1 ; i <= n ; i++)
{
par[i] = i;
sz[i] = 1;
mn[i] = a[i] - b[i];
sumb[i] = b[i];
}
sort(e.begin() , e.end());
reverse(e.begin() , e.end());
int i = 0;
while(q--)
{
long long d = e.back().first , ine = e.back().second;
e.pop_back();
while(i < n - 1 && ed[i][0] <= d)
mrg(ed[i][1] , ed[i][2]) , i++;
ans[ine] = sum;
}
return ans;
}
