#include <bits/stdc++.h> using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> void buildls(ll l, ll r, ll i, vl& tree, ll p, vl& vals){ if (l == r && l < vals.size() && l%2 == p){ tree[i] = vals[l]; return; } else if (l == r){return;} ll mid = (l+r)/2; buildls(l, mid, 2*i, tree, p, vals); buildls(mid +1, r, 2*i+1, tree, p, vals); tree[i] = min(tree[2*i], tree[2*i+1]); return; } void buildg(ll l, ll r, ll i, vl& tree, vl& vals){ if (l == r && l < vals.size()){ tree[i] = vals[l]; return; } else if (l == r){return;} ll mid = (l+r)/2; buildg(l, mid, 2*i, tree, vals); buildg(mid +1, r, 2*i+1, tree, vals); tree[i] = min(tree[2*i], tree[2*i+1]); return; } void update(ll l, ll r, vl& tree, ll i, ll c, ll pos){ if (l == r && l == pos){ tree[i] = c; return; } if (r < pos || l > pos){ return; } ll mid = (l+r)/2; update(l, mid, tree, 2*i, c, pos); update(mid+1,r,tree,2*i+1, c, pos); tree[i] = min(tree[2*i], tree[2*i+1]); return; } ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){ if (L <= l && r <= R){ return tree[i]; } if (r < L || R < l){ return 1e10; } ll mid = (l+r)/2; ll a = query(l, mid, L, R, 2*i, tree); ll b = query(mid+1, r, L, R, 2*i+1, tree); return min(a,b); } std::vector<long long> calculate_costs( std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E){ ll n = W.size(); vll nums; for (ll i = 0; i < n; i++){ nums.push_back({W[i], A[i], B[i]}); } sort(nums.begin(), nums.end()); vl ans; for (ll i = 0; i < E.size(); i++){ ll k = E[i]; vl dp (n+5, 1e10); dp[0] = 0; for (ll j = 0; j < n; j++){ if (j < n){ dp[j+1] = min(dp[j] + nums[j][1], dp[j+1]); } if (j+1 < n){ if (nums[j+1][0] - nums[j][0] <= k){ dp[j+2] = min(dp[j] + nums[j][2] + nums[j+1][2], dp[j+2]); } } if (j+2 < n){ if (nums[j+2][0] - nums[j][0] <= k){ dp[j+3] = min(dp[j] + nums[j][2] + nums[j+2][2] + nums[j+1][1], dp[j+3]); } } } ans.push_back(dp[n]); } return ans; } /*/int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector<int> W, A, B, E; ll n; cin >> n; for (ll i = 0; i < n; i++){ ll a,b,c; cin >>a >> b >> c; W.push_back(a); A.push_back(b); B.push_back(c); } ll q; cin >> q; for (ll i = 0; i < q; i++){ ll a; cin >> a; E.push_back(a); } vl x = calculate_costs(W, A, B, E); for (auto p : x){ cout << p << "\n"; } return 0; } /*/