#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
const int MAX = 1e5 + 5;
int n;
array<int, 2> arr[MAX];
int ans = 0;
struct DSU{
multiset<int> s[MAX];
int par[MAX];
void init(){
for(int i = 0; i < n; i++){
par[i] = -1;
s[i] = {arr[i][1]};
ans += arr[i][1];
}
}
int get(int a){
if(par[a] < 0) return a;
return par[a] = get(par[a]);
}
bool unite(int u, int v){
u = get(u), v = get(v);
if(u == v) return 0;
if(-par[u] < -par[v]) swap(u, v);
if(s[u].size() & 1) ans -= *s[u].begin();
if(s[v].size() & 1) ans -= *s[v].begin();
par[u] += par[v];
par[v] = u;
for(int a : s[v]) s[u].insert(a);
if(s[u].size() & 1) ans += *s[u].begin();
return 1;
}
};
DSU dsu;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
n = W.size();
for(int i = 0; i < n; i++){
arr[i] = {W[i], A[i] - B[i]};
ans += B[i];
}
sort(arr, arr + n);
vector<pii> v;
for(int i = 0; i < n - 1; i++){
v.push_back({arr[i + 1][0] - arr[i][0], i});
}
sort(all(v));
reverse(all(v));
vector<pii> Q;
for(int i = 0; i < E.size(); i++) Q.push_back({E[i], i});
dsu.init();
sort(all(Q));
vector<ll> res(Q.size(), 0);
for(pii d : Q){
while(v.size() && v.back().first <= d.first){
dsu.unite(v.back().second, v.back().second + 1);
v.pop_back();
}
res[d.second] = ans;
}
return res;
}
