#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define ll long long
vector<ll> S,parent,mn_g;
int find(int node){
if(parent[node] == node)
return node;
return parent[node] = find(parent[node]);
}
void unite(int a,int b){
a = find(a),b = find(b);
parent[b] = parent[a];
S[a] += S[b];
mn_g[a] = min(mn_g[a],mn_g[b]);
}
vector<ll> calculate_costs(vector<int> W,vector<int> A,vector<int> B,vector<int> E){
int n = W.size();
S.assign(W.size(),1);
parent.assign(W.size(),0);
mn_g.assign(W.size(),1e18);
vector<pair<int,int>> w;
for(int i=0;i<n;i++){
parent[i] = i;
}
for(int i=0;i<n;i++){
mn_g[i] = A[i]-B[i];
w.push_back(make_pair(W[i],i));
}
vector<pair<int,ll>> possAns; // D,ans
ll cur_ans = 0;
ll sum_mn = 0;
for(int i=0;i<n;i++){
cur_ans += B[i];
sum_mn += mn_g[i];
}
possAns.push_back(make_pair(-1,cur_ans+sum_mn));
vector<pair<int,pair<int,int>>> process;
sort(w.begin(),w.end());
for(int i=0;i<n-1;i++){
int a = w[i].second,b = w[i+1].second;
process.push_back(make_pair(w[i+1].first-w[i].first,
make_pair(a,b)));
}
sort(process.begin(),process.end());
for(auto p_cur : process){
int a = find(p_cur.second.first),b = find(p_cur.second.second);
int d = p_cur.first;
if(S[a]%2 == 1 && S[b]%2 == 0){
sum_mn -= mn_g[a];
sum_mn += min(mn_g[a],mn_g[b]);
}
else if(S[a]%2 == 0 && S[b]%2 == 1){
sum_mn -= mn_g[b];
sum_mn += min(mn_g[a],mn_g[b]);
}
else if(S[a]%2 == 1 && S[b]%2 == 1){
sum_mn -= mn_g[b]+mn_g[a];
}
unite(a,b);
possAns.push_back(make_pair(d,cur_ans+sum_mn));
}
vector<pair<int,int>> defAns;
for(int i=0;i<possAns.size();i++){
ll mn = possAns[i].second;
while(i+1 < n && possAns[i].first == possAns[i+1].first){
mn = min(mn,possAns[i+1].second);
i++;
}
defAns.push_back(make_pair(i,mn));
}
vector<ll> ans;
for(int i=0;i<(int)E.size();i++){
int d = E[i];
auto it = upper_bound(defAns.begin(),def.end(),make_pair(d,(ll)1e18));
it--;
pair<int,ll> p = *it;
ans.push_back(p.second);
}
return ans;
}
