#include <bits/stdc++.h>
// This solves subtask 4.
using namespace std;
vector<long long> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E) {
int N = W.size();
int Q = E.size();
vector<tuple<int, int, int>> artifacts(N);
for (int i = 0; i < N; ++i) {
artifacts[i] = make_tuple(W[i], A[i], B[i]);
}
// Sort artifacts by weight ascending first
sort(artifacts.begin(), artifacts.end());
// Results for each D in E
vector<long long> results(Q);
for (int q = 0; q < Q; ++q) {
int D = E[q];
// DP[i] stores the minimum cost for sending items from 0 to i.
vector<long long> dp(N, ULLONG_MAX);
dp[0] = get<1>(artifacts[0]); // Base case: Send 0 on its own.
for (int i = 1; i < N; ++i) {
// Case 1: send artifact i alone
dp[i] = get<1>(artifacts[i]) + dp[i-1];
// Case 2: try to pair i with i-1
if ((get<0>(artifacts[i]) - get<0>(artifacts[i-1])) <= D)
{
long long costLeft = i-2 >= 0 ? dp[i-2] : 0;
long long costFromPairingWithNextOne = get<2>(artifacts[i]) + get<2>(artifacts[i-1]) + costLeft;
dp[i] = min(dp[i], costFromPairingWithNextOne);
}
// Case 3: Try to pair i with i-2
if (((get<0>(artifacts[i]) - get<0>(artifacts[i-2])) <= D) && (i-2 >= 0))
{
long long costLeftFromIMinus3 = i-3 >= 0 ? dp[i-3] : 0;
long long costFromPairingWithIMinus2 = get<2>(artifacts[i]) + get<1>(artifacts[i-1]) + get<2>(artifacts[i-2]) + costLeftFromIMinus3;
dp[i] = min(dp[i], costFromPairingWithIMinus2);
}
//cout << dp[i] << endl;
}
results[q] = dp[N-1];
}
return results;
}
