#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
vector<pair<int , int>> arr , e;
vector<pair<int , pair<int , int>>> w;
int n , q , par[100001] , choto[100001] , koita[100001] , ek , dui;
long long sum , one , two , uttor ;
int findpar( int me ) {
if( par[me] == me ) return me;
else{
par[me] = findpar( par[me] );
return par[me];
}
}
void comb( int a , int b ) {
int aa = findpar( a );
int bb = findpar( b );
if( (koita[aa] % 2) == 1 ) {
uttor -= (ll)choto[aa];
}
if( (koita[bb] % 2) == 1 ) {
uttor -= (ll)choto[bb];
}
par[bb] = aa;
koita[aa] += koita[bb];
choto[aa] = min( choto[aa] , choto[bb] );
if( koita[aa] % 2 == 1 ) {
uttor += (ll)choto[aa];
}
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
n = (int)W.size();
q = (int)E.size();
w.clear();
e.clear();
for( int z = 0; z < n; z++ ){
w.push_back({W[z] , {A[z] , B[z]}});
}
for( int z = 0; z < q; z++ ){
e.push_back({E[z] , z});
}
sort( e.begin() , e.end() );
sort( w.begin() , w.end() );
arr.clear();
for( int z = 1; z < n; z++ ) {
arr.push_back({w[z].first - w[z - 1].first , (z - 1) });
}
sort( arr.begin() , arr.end() );
sum = 0;
uttor = 0;
for( int z = 0; z < n; z++ ) {
sum += (long long)w[z].second.second;
choto[z] = w[z].second.first - w[z].second.second;
par[z] = z;
koita[z] = 1;
uttor += (ll)w[z].second.first;
}
int here = 0;
vector<long long> ans(q);
cerr << "lol" << "\n";
for( int z = 0; z < q; z++ ) {
while( here < n - 1 && e[z].first >= arr[here].first ) {
comb( arr[here].second , arr[here].second + 1 );
here++;
}
ans[e[z].second] = uttor;
for( int z = 0; z < n; z++ ) {
cerr << choto[z] << " ";
}
cerr << "\n";
}
return ans;
}
