#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int inf = 1e9 + 7;
const int N = 1e5 + 7;
int par[N] , len[N] , cand[2][N] , jump[N];
int find(int a){
if(par[a] == a)return a;
return par[a] = find(par[a]);
}
void merge(int a , int b){
a = find(a) , b = find(b);
if(a == b)return;
jump[a] = min(jump[a] , jump[b]);
cand[0][a] = min(cand[0][a] , cand[len[a] & 1][b]);
cand[1][a] = min(cand[1][a] , cand[!(len[a] & 1)][b]);
len[a] += len[b];
par[b] = a;
}
int getans(int a){
a = find(a);
if(len[a] & 1)
return min(cand[0][a] , jump[a]);
else
return 0;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) {
iota(par , par + N , 0);
fill(len , len + N , 1);
fill(cand[0] , cand[0] + N , 0);
fill(cand[1] , cand[1] + N , inf);
fill(jump , jump + N , inf);
long long cur_ans = 0 , fixated_ans = 0;
int n = sz(W);
vector<array<int,2>>arr(n);
for(int i = 0;i<n;i++){
arr[i] = {W[i] , A[i] - B[i]};
fixated_ans += B[i];
}
sort(all(arr));
// cout << "arr : ";for(auto itr : arr)cout << itr[0] << "," << itr[1] << " ";cout << endl;
int q = sz(E);
vector<pair<int,int>>query(q);
vector<long long> ans(q);
for(int i = 0;i<q;i++)
query[i] = {E[i] , i};
sort(all(query));
priority_queue<array<int,3>>pq;// -cost , ind1 , ind2
for(int i = 0;i<n-1;i++)
pq.push({arr[i][0] - arr[i+1][0] , i , i+1});
for(int i = 0;i<n;i++){
cand[0][i] = arr[i][1];
cur_ans += arr[i][1];
}
// cout << "fixated_ans : " << fixated_ans << endl;
// cout << "cur_ans : " << cur_ans << endl;
for(auto itr : query){
int qtime = itr.first;
int qind = itr.second;
// cout << "query : " << qtime << " " << qind << endl;
while(!pq.empty() and -pq.top()[0] <= qtime){
auto tmp = pq.top();
// cout << "tmp : " << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl;
pq.pop();
if(tmp[2] - tmp[1] == 1){
cur_ans -= getans(tmp[1]);
cur_ans -= getans(tmp[2]);
merge(tmp[1] , tmp[2]);
cur_ans += getans(tmp[1]);
if(tmp[1] + 2 < n)
pq.push({arr[tmp[1]][0] - arr[tmp[1]+2][0] , tmp[1] , tmp[1] + 2});
}
else{// == 2
assert(find(tmp[1]) == find(tmp[2]));
cur_ans -= getans(tmp[1]);
int repr = find(tmp[1]);
jump[repr] = min(jump[repr] , arr[tmp[1]+1][1]);
cur_ans += getans(tmp[1]);
}
// cout << "cur_ans : " << cur_ans << endl;
}
ans[qind] = cur_ans + fixated_ans;
}
return ans;
}
