#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
const ll NEG_INF = -1e18;
// Structure for an artifact.
struct Artifact {
int w, A, B, s; // weight, solo cost, paired cost, saving = A - B
};
// Segment Tree for range maximum queries.
struct SegTree {
int n;
vector<ll> tree;
SegTree(int n_) : n(n_) {
tree.assign(4*n, NEG_INF);
}
void update(int idx, int l, int r, int pos, ll val) {
if (l == r) {
tree[idx] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(2*idx, l, mid, pos, val);
else
update(2*idx+1, mid+1, r, pos, val);
tree[idx] = max(tree[2*idx], tree[2*idx+1]);
}
ll query(int idx, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return NEG_INF;
if (ql <= l && r <= qr) return tree[idx];
int mid = (l + r) / 2;
return max(query(2*idx, l, mid, ql, qr),
query(2*idx+1, mid+1, r, ql, qr));
}
void update(int pos, ll val) {
update(1, 0, n-1, pos, val);
}
ll query(int l, int r) {
if(l > r) return NEG_INF;
return query(1, 0, n-1, l, r);
}
};
// Compute the answer for one query with given D.
ll computeAnswer(const vector<Artifact>& artifacts, ll base, int D) {
int n = artifacts.size();
// dp[i] = maximum total saving using artifacts 0..i (in sorted order)
vector<ll> dp(n, 0);
// X[j] = (if j == 0 then s[0] else dp[j-1] + s[j])
vector<ll> X(n, 0);
// Build segment tree over indices [0, n-1] for X values.
SegTree seg(n);
// For artifact 0:
dp[0] = 0; // cannot pair artifact0 alone
X[0] = artifacts[0].s; // (dp[-1] assumed 0)
seg.update(0, X[0]);
// For artifacts 1 to n-1:
for (int i = 1; i < n; i++) {
// Find L: the first index with weight >= artifacts[i].w - D.
int low = 0, high = i;
int L = i; // default: no candidate
while(low < high) {
int mid = (low + high) / 2;
if (artifacts[mid].w >= artifacts[i].w - D)
high = mid;
else
low = mid + 1;
}
L = low;
ll candidate = NEG_INF;
if (L <= i-1 && artifacts[i].w - artifacts[L].w <= D) {
candidate = artifacts[i].s + seg.query(L, i-1);
}
dp[i] = max(dp[i-1], candidate);
// Set X[i] = dp[i-1] + s[i] (artifact i remains free to be paired later if not paired now)
X[i] = dp[i-1] + artifacts[i].s;
seg.update(i, X[i]);
}
// Minimum total cost = base cost - total saving
return base - dp[n-1];
}
// Main procedure to answer Q queries.
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size();
int Q = E.size();
vector<ll> ans(Q, 0);
// Build artifacts vector.
vector<Artifact> artifacts(n);
ll base = 0;
for (int i = 0; i < n; i++) {
artifacts[i].w = W[i];
artifacts[i].A = A[i];
artifacts[i].B = B[i];
artifacts[i].s = A[i] - B[i];
base += A[i];
}
// Sort artifacts by weight.
sort(artifacts.begin(), artifacts.end(), [](const Artifact& a, const Artifact& b) {
return a.w < b.w;
});
// For each query, run the DP.
// (Note: This is O(n log n) per query. For worst-case constraints further offline processing is needed.)
for (int j = 0; j < Q; j++) {
ans[j] = computeAnswer(artifacts, base, E[j]);
}
return ans;
}
// Sample main to test the sample test-case.
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
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 j = 0; j < Q; j++){
cin >> E[j];
}
vector<ll> R = calculate_costs(W, A, B, E);
for (auto &val : R)
cout << val << "\n";
return 0;
}
