#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
const int N = 1e5+100;
int _n;
ll T[N*2];
void build(int n){
_n = n;
for(int j = 0; j <= 2*n+2; ++j) T[j] = 1e18;
}
void upd(int p, ll val){
++p;
T[p += _n] = val;
for(p >>= 1; p; p >>= 1) T[p] = min(T[p<<1], T[p<<1|1]);
}
ll get(int l, int r){
if(l > r) return 1e18;
ll res = 1e18;
++l, ++r;
l += _n;
r += _n + 1;
for(; l < r; l >>= 1, r >>= 1){
if(l&1) res = min(res, T[l++]);
if(r&1) res = min(res, T[--r]);
}
return res;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int q = (int) E.size();
int n = (int) W.size();
build(n);
vector<array<ll, 3>> C;
for(int i = 0; i < n; ++i) C.pb({W[i], A[i], B[i]});
sort(all(C));
vector<ll> pref(n);
pref[0] = C[0][1];
for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + C[i][1];
function<ll(int, int)> get2 = [&](int l, int r){
return pref[r] - (l <= 0 ? 0 : pref[l - 1]);
};
vector<ll> res;
for(ll D: E){
vector<ll> DP(n);
DP[0] = C[0][1];
build(n);
upd(0, C[0][2]-pref[0]);
for(int i = 1; i < n; ++i){
int j = lower_bound(all(C), array<ll,3>{C[i][0]-D, -1ll, -1ll}) - C.begin();
DP[i] = min(DP[i - 1] + C[i][1], pref[i-1] + get(j, i-1) + C[i][2]);
upd(i, DP[i-1] - pref[i] + C[i][2]);
}
res.pb(DP.back());
}
return res;
}
