#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long
#define pii pair<int, int>
#define ff first
#define ss second
#define sz size
#define rsz resize
#define pb push_back
#define ass assign
#define endl '\n'
#define all(x) (x).begin(),(x).end()
vector<lli> dp;
int n;
// vector<int> w, a, b, ind;
vector<tuple<int, int, int>> v;
lli calc(int i, int d){
if(i>=n) return 0;
if(dp[i]!=-1)return dp[i];
dp[i]=1e18;
lli soma=0;
for(int j=i+1; j<n; j++){
if(abs(get<0>(v[i])-get<0>(v[j]))<=d){
dp[i]=min(dp[i], calc(j+1, d)+get<2>(v[i])+get<2>(v[j])+soma);
soma+=get<1>(v[j]);
}
else break;
}
// if(i+1<n){
// if(abs(get<0>(v[i])-get<0>(v[i+1]))<=d)dp[i]=calc(i+2, d)+get<2>(v[i])+get<2>(v[i+1]);
// }
dp[i]=min(dp[i], calc(i+1, d)+get<1>(v[i]));
return dp[i];
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
// w=W;
// a=A;
// b=B;
int q=E.size();
n=W.size();
v.rsz(n);
for(int i=0; i<n; i++){
v[i]={W[i], A[i], B[i]};
// ind[i]=i;
}
// sort(all(ind), [&](int a, int b){
// return w[a]<w[b];
// });
sort(all(v));
// lli soma=0;
// for(int i=0; i<n; i++){
// soma+=B[i];
// }
// // cout << soma<<endl;
// lli resp=1e18;
// if(n%2==1){
// for(int i=0; i<n; i++){
// resp=min(resp, soma-B[i]+A[i]);
// // cout << resp << endl;
// }
// }else resp=soma;
vector<lli> R(q);
for(int i=0; i<q; i++){
dp.ass(n, -1);
R[i]=calc(0, E[i]);
}
return R;
}
