#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using tripla = tuple<ll, ll, ll>;
const ll inf = 1e18;
struct Evento{
ll prior, a, b; Evento( ll prior, ll a, ll b ) : prior(prior), a(a), b(b) {}
bool operator < ( Evento e ){
if( prior != e.prior ) return prior < e.prior;
if( a != e.a ) return a < e.a;
return b < e.b;
}
}; vector<Evento> line;
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e ){
int n = w.size();
int q = e.size();
vector<tripla> v;
ll tot = 0;
vector<ll> total(n), pai(n), pares(n, inf), impares(n), livres(n, inf), tam(n, 1);
iota( pai.begin(), pai.end(), 0 );
map<ll, int> cont;
cont[-inf] = 1;
cont[inf] = 1;
for( int i = 0; i < n; i++ ){
v.emplace_back( w[i], a[i], b[i] );
tot += a[i];
cont[w[i]]++;
}
sort( v.begin(), v.end() );
for( int i = 0; i < n; i++ ){
auto [w1, a1, b1] = v[i];
if( cont[w1] >= 3 ) line.push_back( Evento( 0, n, i ) );
else if( cont[w1] == 2 ){
ll dist = inf;
for( int j = max( 0, i - 3 ); j < min( n - 1, i + 3); j++ ) if( get<0>(v[j]) != w1 ) dist = min( dist, (ll)abs(w1 - get<0>(v[j])));
if( dist != inf ) line.push_back( Evento( dist, n, i ) );
}
if( i + 1 < n ){
auto [w2, a2, b2] = v[i + 1];
line.push_back( Evento( w2 - w1, i, i + 1 ) );
if( i > 0 ){
auto [w3, a3, b3] = v[i - 1];
line.push_back( Evento( w2 - w3, n, i ) );
}
}
total[i] = a1 - b1;
impares[i] = a1 - b1;
}
for( int i = 0; i < q; i++ ){
line.push_back( Evento( e[i], n + 1, i ) );
}
sort( line.begin(), line.end() );
vector<ll> resp(q);
auto get_total = [&]( int id ){
if( tam[id]%2 == 0 ) return 0LL;
return min( livres[id], impares[id] );
};
function<int(int)> find = [&]( int a ){
return (( pai[a] == a ) ? a : pai[a] = find(pai[a]));
};
auto join = [&]( int a, int b ){
a = find(a); b = find(b);
if( a == b ) return;
tot -= (total[a] + total[b]);
if( tam[a]%2 == 1 ){
impares[a] = min( impares[a], pares[b] );
pares[a] = min( pares[a], impares[b] );
}
else{
impares[a] = min( impares[a], impares[b] );
pares[a] = min( pares[a], pares[b] );
}
livres[a] = min( livres[a], livres[b] );
tam[a] += tam[b];
total[a] = get_total(a);
tot += total[a];
pai[b] = a;
};
for( auto cur : line ){
if( cur.a == n + 1 ) resp[cur.b] = tot;
else if( cur.a == n ){
auto [w1, a1, b1] = v[cur.b];
int id = find(cur.b);
livres[id] = min( livres[id], a1 - b1 );
tot -= total[id];
total[id] = get_total(id);
tot += total[id];
}
else join( cur.a, cur.b );
}
return resp;
}
