#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 9e18;
struct Artifact {
ll w;
ll a;
ll b;
};
const ll MAX_SZ = 1e5 + 10;
ll memo[MAX_SZ];
ll dp(ll ind, ll D, vector<Artifact> &artifacts) {
ll N = (ll)artifacts.size();
if (ind == N) return 0;
if (memo[ind] != -1LL) {
return memo[ind];
}
ll res1 = dp(ind + 1, D, artifacts) + artifacts[ind].a;
ll res2 = INF;
ll notIncluded = 0;
for (ll newInd = ind + 1; newInd < N; newInd++) {
if (artifacts[newInd].w - artifacts[ind].w <= D) {
res2 = min(
res2,
dp(newInd + 1, D, artifacts) + artifacts[ind].b + artifacts[newInd].b + notIncluded
);
}
notIncluded += artifacts[newInd].a;
}
return memo[ind] = min(res1, res2);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
ll Q = (ll)E.size();
ll N = (ll)A.size();
vector<ll> R(Q);
vector<Artifact> artifacts;
artifacts.reserve(N);
for (ll i = 0; i < N; i++) {
artifacts.push_back(Artifact{W[i], A[i], B[i]});
}
sort(artifacts.begin(), artifacts.end(), [&](Artifact &a, Artifact &b) {
if (a.w == b.w) {
if (a.a == b.a) {
return a.b < b.b;
}
return a.a < b.a;
}
return a.w < b.w;
});
for (ll queryInd = 0; queryInd < Q; queryInd++) {
memset(memo, -1LL, sizeof(memo));
ll res = dp(0, E[queryInd], artifacts);
R[queryInd] = res;
}
return R;
}
