#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
vector<int> w = W, a = A, b = B, e = E;
int n = w.size(), q = e.size();
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int l, int r)
{
return w[l] < w[r];
});
vector<long long> RES(q);
for(int i = 0; i < q; i++)
{
vector<int> par(n), sz(n + 1, 1);
iota(par.begin(), par.end(), 0);
auto find = [&](auto self, int u) -> int
{
return par[u] = (par[u] == u ? u : self(self, par[u]));
};
auto unite = [&](int u, int v) -> bool
{
u = find(find, u);
v = find(find, v);
if(u == v)
return false;
if(sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
par[u] = v;
return true;
};
int d = e[i];
for(int j = 0; j + 1 < n; j++)
{
int k = ord[j];
int l = ord[j + 1];
if(w[l] - w[k] <= d)
{
unite(l, k);
}
}
map<int, vector<int>> mp;
for(int j = 0; j < n; j++)
{
int k = ord[j];
k = find(find, k);
mp[k].push_back(ord[j]);
}
long long res = 0;
for(auto [f, s]: mp)
{
if((int)s.size() % 2 == 0)
{
for(int j = 0; j < (int)s.size(); j++)
res += b[s[j]];
}
else
{
for(int j = 0; j < (int)s.size(); j++)
res += b[s[j]];
long long mn = LLONG_MAX;
int idx = -1;
for(int j = 0; j < (int)s.size(); j++)
{
if(!(j & 1))
{
mn = min(mn, (long long)a[s[j]] - b[s[j]]);
}
else
{
if(w[s[j + 1]] - w[s[j - 1]] <= d)
{
mn = min(mn, (long long)a[s[j]] - b[s[j]]);
}
}
}
res += mn;
}
}
RES[i] = res;
}
return RES;
}
