#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " -> " << x << "\n"
using namespace std;
using ll = long long;
vector<ll> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E){
int n = A.size();
int q = E.size();
static const ll INF = 1e15;
vector<ll> R(q,INF);
ll S = accumulate(B.begin(),B.end(),0ll);
vector<int> idx(n);
iota(idx.begin(),idx.end(),0);
sort(idx.begin(),idx.end(),[&](int a,int b)->bool{
return W[a] < W[b];
});
for(int i = 0; i < q; ++i){
int D = E[i];
ll dp[n][2][2];
dp[0][0][0] = A[idx[0]];
dp[0][0][1] = INF;
dp[0][1][0] = INF;
dp[0][1][1] = B[idx[0]];
vector<ll> suff(n);
suff[n-1] = A[idx[n-1]];
for(int i = n-2; i >= 0; --i){
suff[i] = suff[i+1]+A[idx[i+1]];
}
vector<vector<ll>> C(2,vector<ll>(n));
C[0][0] = INF;
C[1][0] = dp[0][1][1]+suff[1];
int l = 0;
multiset<ll> st1;
multiset<ll> st2;
for(int i = 1; i < n; ++i) {
dp[i][0][0] = min<ll>(dp[i-1][1][0],dp[i-1][0][0]) + A[idx[i]];
dp[i][0][1] = min<ll>(dp[i-1][1][1],dp[i-1][0][1]) + A[idx[i]];
st1.insert(C[1][i-1]);st2.insert(C[0][i-1]);
while(W[idx[l]]<W[idx[i]]-D){
st1.erase(st1.find(C[1][l]));
st2.erase(st2.find(C[0][l]));
++l;
}
//dbg(*st1.begin());
dp[i][1][1] = suff[0]-suff[i]+B[idx[i]];
dp[i][1][1] = min<ll>(dp[i-1][1][0],dp[i-1][0][0])+B[idx[i]];
if(l!=i){
dp[i][1][0] = *(st1.begin()) - suff[i] + B[idx[i]];
dp[i][1][1] = min<ll>(*(st2.begin()) - suff[i] + B[idx[i]],dp[i][1][1]);
}else{
dp[i][1][0] = INF;
}
ll buf = 0;
if(i!=n-1)buf=suff[i+1];
C[0][i] = dp[i][1][0] + buf;
C[1][i] = dp[i][1][1] + buf;
//dbg(dp[i][1][1]);
}
dbg(endl);
R[i] = min<ll>(dp[n-1][0][0],dp[n-1][1][0]);
}
return R;
}
// signed main(void) {
// cin.tie(0)->sync_with_stdio(0);
// int N;
// cin >> N;
// vector<int> W(N),A(N),B(N);
// for(int i = 0; i < N; ++i){
// cin >> W[i] >> A[i] >> B[i];
// }
// int Q;
// cin >> Q;
// vector<int> E(Q);
// for(int i = 0; i < Q; ++i) {
// cin >> E[i];
// }
// vector<ll> costs = calculate_costs(W,A,B,E);
// for(auto &c : costs){
// cout << c << endl;
// }
// }
