#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;
const ll INF = 1e18;
ll par[N], siz[N], tot, ans[N], mini[N][2] ,L[N], bsum[N], acik[N];
vector<array<ll,3>> ar;
ll find(ll a){
if(par[a] == a) return a;
return par[a] = find(par[a]);
}
void unite(ll a,ll b){
if(a + 2 == b){
acik[find(a)] = min(acik[find(a)], ar[a + 1][2] - ar[a + 1][1]);
return;
}
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];
L[a] = min(L[a], L[b]);
tot -= (ans[a] + ans[b]);
for(int i=0;i<2;i++) mini[a][i] = min(mini[a][i], mini[b][i]);
bsum[a] += bsum[b];
if(siz[a] % 2){
ans[a] = bsum[a] + mini[a][L[a]&1];
min(ans[a], bsum[a] + acik[a]);
}
else{
ans[a] = bsum[a];
}
tot += ans[a];
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
ll n = sz(W);
ar.clear();
for(ll 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(ll i=0;i<q;i++){
ll a = E[i];
que.push_back({a, i});
}
sort(all(que));
tot = 0;
for(ll i=0;i<n;i++){
L[i] = par[i] = i;
acik[i] = INF;
siz[i] = 1;
mini[i][i&1] = ar[i][2] - ar[i][1];
bsum[i] = ar[i][1];
ans[i] = ar[i][2];
tot += ans[i];
}
vector<array<ll,3>> Merge;
for(ll i=1;i<n;i++) Merge.push_back({ar[i][0] - ar[i - 1][0], 0, i - 1});
for(ll i=1;i+1<n;i++) Merge.push_back({ar[i+1][0] - ar[i-1][0], 1, i - 1});
sort(all(Merge));
ll ptr = 0;
for(array<ll,2> x : que){
while(ptr < sz(Merge) && Merge[ptr][0] <= x[0]){
if(Merge[ptr][1] == 0) unite(Merge[ptr][2] , Merge[ptr][2] + 1);
else unite(Merge[ptr][2], Merge[ptr][2] + 2);
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--) _();
}*/
