#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = signed;
struct Query {
int dis, id_qry;
auto operator<=>(const Query&) const = default;
};
struct Artifact {
int weight, value;
auto operator<=>(const Artifact&) const = default;
};
int solve(const vector<Artifact> &arts, int dis) {
int nb_arts = arts.size();
vector<int> dp(nb_arts+1, 0);
deque<Artifact> stk;
for (int i = nb_arts-1; i >= 0; --i) {
dp[i] = dp[i+1];
while (!stk.empty() && stk.front().weight - arts[i].weight > dis)
stk.pop_front();
if (!stk.empty())
dp[i] = max(dp[i], arts[i].value + stk.front().value);
int add = arts[i].value + dp[i+1];
while (!stk.empty() && stk.back().value <= add)
stk.pop_back();
stk.push_back({arts[i].weight, add});
}
return dp[0];
}
vector<int> solve(vector<Artifact> artifacts, vector<Query> queries) {
vector<int> answer(queries.size(), 0);
sort(artifacts.begin(), artifacts.end());
sort(queries.begin(), queries.end());
for (auto [dis, id_qry] : queries) {
answer[id_qry] = solve(artifacts, dis);
}
return answer;
}
vector<int> calculate_costs(vector<i32> W, vector<i32> A, vector<i32> B, vector<i32> E) {
int nb_artifacts = W.size(), nb_queries = E.size();
vector<Artifact> artifacts;
for (int i = 0; i < nb_artifacts; ++i) {
artifacts.push_back({W[i], A[i] - B[i]});
}
vector<Query> queries;
for (int i = 0; i < nb_queries; ++i) {
queries.push_back({E[i], i});
}
vector<int> answer = solve(artifacts, queries);
int sum_A = accumulate(A.begin(), A.end(), 0ll);
for (int &x : answer) {
x = sum_A - x;
}
return answer;
}
