#include "bits/stdc++.h"
#include "nile.h"
#define ll long long
#define sz(v) (ll) v.size()
#define all(v) v.begin(),v.end()
using namespace std;
const ll N = 1e5 + 5;
ll par[N], siz[N], tot, ans[N], mini[N], bsum[N];
ll find(ll a){
if(par[a] == a) return a;
return par[a] = find(par[a]);
}
void unite(int a,int b){
//cout << "birles : " << a << ' ' << b << '\n';
//cout << "onceki cost : " << tot << '\n';
a=find(a),b=find(b);
if(a==b) return;
if(siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
//cout << "cikar : " << ans[a] + ans[b] << '\n';
tot -= (ans[a] + ans[b]);
mini[a] = min(mini[a], mini[b]);
bsum[a] += bsum[b];
ans[a] = (siz[a] % 2 ? bsum[a] + mini[a] : bsum[a]);
tot += ans[a];
//cout << "ekle : " << ans[a] << '\n';
//cout << "new cost : " <<tot << '\n';
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
ll n = sz(W);
vector<array<ll,3>> ar;
for(int i=0;i<n;i++){
ll a = W[i], b = B[i], c = A[i];
ar.push_back({a, b, c});
}
sort(all(ar));
ll q = sz(E);
vector<ll> Res(q, 0);
vector<array<ll,2>> que;
for(int i=0;i<q;i++){
ll a = E[i];
que.push_back({a, i});
}
sort(all(que));
tot = 0;
for(int i=0;i<n;i++){
par[i] = i;
siz[i] = 1;
mini[i] = ar[i][2] - ar[i][1];
//cout << " i : " << mini[i] << '\n';
bsum[i] = ar[i][1];
ans[i] = ar[i][2];
//cout << "ansi : " << ans[i] << '\n';
tot += ans[i];
}
vector<array<ll,2>> Merge;
for(int i=1;i<n;i++){
Merge.push_back({ar[i][0] - ar[i - 1][0], i - 1});
}
sort(all(Merge));
ll ptr = 0;
for(auto x : que){
//cout << "suan : " << x[0] << '\n';
while(ptr < sz(Merge) && Merge[ptr][0] <= x[0]){
//cout << Merge[ptr][0] << ' ' << Merge[ptr][1] << '\n';
unite(Merge[ptr][1], Merge[ptr][1] + 1);
ptr++;
}
Res[x[1]] = tot;
}
return Res;
}
/*void _(){
int n;
cin >> n;
vector<array<int,3>> ar;
for(int i=0;i<n;i++){
int a,b,c;
cin >> a >> b >> c;
ar.push_back({a, c, b});
}
sort(all(ar));
int q; cin >> q;
vector<int> Res(q, 0);
vector<array<int,2>> que;
for(int i=0;i<q;i++){
int a; cin >> a;
que.push_back({a, i});
}
sort(all(que));
tot = 0;
for(int i=0;i<n;i++){
par[i] = i;
siz[i] = 1;
mini[i] = ar[i][2] - ar[i][1];
//cout << " i : " << mini[i] << '\n';
bsum[i] = ar[i][1];
ans[i] = ar[i][2];
//cout << "ansi : " << ans[i] << '\n';
tot += ans[i];
}
vector<array<int,2>> Merge;
for(int i=1;i<n;i++){
Merge.push_back({ar[i][0] - ar[i - 1][0], i - 1});
}
sort(all(Merge));
int ptr = 0;
for(auto x : que){
//cout << "suan : " << x[0] << '\n';
while(ptr < sz(Merge) && Merge[ptr][0] <= x[0]){
//cout << Merge[ptr][0] << ' ' << Merge[ptr][1] << '\n';
unite(Merge[ptr][1], Merge[ptr][1] + 1);
ptr++;
}
Res[x[1]] = tot;
}
for(int i=0;i<q;i++){
cout << Res[i] << '\n';
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tc=1;//cin >> tc;
while(tc--) _();
}*/
