#include <bits/stdc++.h>
// This obtains 47 points.
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());
/*
for (int i = 0; i < artifacts.size(); ++i)
{
cout << get<0>(artifacts[i]) << " " << get<1>(artifacts[i]) << " " << get<2>(artifacts[i]) << endl;
}
*/
// 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 with everything below it that's possible
// By sending everything in between on its own. Them being paired will be considered on their turn of the DP.
long long a_Cost_In_Between = 0;
for (int j = i-1; j >= 0; --j) {
int i_weight = get<0>(artifacts[i]);
int j_weight = get<0>(artifacts[j]);
if (i_weight - j_weight > D) break;
// Accumulate the A cost of the artifacts in the range j, [j+1, ... , i-1] , i
int aCost = 0;
if (j+1 < i)
{
aCost = get<1>(artifacts[j+1]);
}
a_Cost_In_Between += aCost;
long long costFromPairing = get<2>(artifacts[i]) + get<2>(artifacts[j]) + a_Cost_In_Between;
long long leftOverCost = j-1 >= 0 ? dp[j-1] : 0;
dp[i] = min(dp[i], costFromPairing + leftOverCost);
}
//cout << dp[i] << endl;
}
results[q] = dp[N-1];
//std::cout << results[q] << endl;
}
return results;
}
