#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll,ll>;
#define all(x) (x).begin(),(x).end()
vector<ll> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E) {
int N = (int)W.size();
int Q = (int)E.size();
vector<ll> R(Q, 0);
vector<pi> V;
for(int i = 0; i < N; i++) V.emplace_back(W[i], i);
sort(all(V));
for(int q = 0; q < Q; q++)
{
ll D = E[q];
ll ans = 0;
vector<vector<pi>> groups;
vector<pi> cur;
cur.emplace_back(V[0]);
for(int i = 1; i < N; i++)
{
if(V[i].first - cur.back().first <= D)
{
cur.emplace_back(V[i]);
}
else
{
groups.push_back(cur);
cur = {V[i]};
}
}
groups.push_back(cur);
for(auto &e : groups)
{
int n = e.size();
if(n%2 == 0)
{
for(auto i : e) ans += B[i.second];
continue;
}
ll sum = 0;
for(auto i : e) sum += B[i.second];
ll best = LLONG_MAX;
for(ll i = 0; i < n; i++)
{
sum += A[e[i].second]-B[e[i].second];
if((i%2 == 0 && (n-i-1)%2 == 0) ||
(i != 0 && i != n-1 && e[i+1].first-e[i-1].first <= D))
{
best = min(best, sum);
}
sum -= A[e[i].second]-B[e[i].second];
}
ans += best;
}
R[q] = ans;
}
return R;
}
