#include "nile.h"
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = W.size(), Q = E.size();
vector<int> X(N); iota(X.begin(), X.end(), 0);
sort(X.begin(), X.end(), [&](const int a, const int b) {return W[a] < W[b];} );
vector<ll> res(Q);
auto solve = [&](int D) {
vector<array<ll, 3>> dp(N+1, {INF, INF, INF});
dp[N][0] = dp[N][1] = dp[N][2] = 0;
/*
dp[i][0] -> by self
dp[i][1] -> with i-1
dp[i][2] -> with i-2
*/
auto getM = [&](int i) -> ll {return min(dp[i][0], min(dp[i][1], dp[i][2])); };
for(int i = N-1; i >= 0; i--) {
dp[i][0] = getM(i+1) + A[X[i]];
if (i+1 < N && W[X[i+1]] - W[X[i]] <= D) {
dp[i][1] = getM(i+2) + B[X[i]] + B[X[i+1]];
}
if (i+2 < N && W[X[i+2]] - W[X[i]] <= D) {
dp[i][2] = getM(i+3) + B[X[i]] + A[X[i+1]] + B[X[i+2]];
}
// cout << i << ' ' << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << endl;
}
return getM(0);
};
for(int i = 0; i < Q; i++) res[i] = solve(E[i]);
return res;
}
