#include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct ura
{
int a,b,w;
};
bool cmp(ura a, ura b)
{
return a.w<b.w;
}
ura vec[100005];
long long dp[100005][3];
int n;
long long inf=1e16;
long long solve(int d)
{
for(int i=1;i<=n;i++)
{
dp[i][0]=inf;
dp[i][1]=inf;
}
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
dp[i][0]=min(dp[i][0],dp[i-1][0]+vec[i].a);
if(i>=2 && vec[i].w-vec[i-1].w<=d)
dp[i][0]=min(dp[i][0],dp[i-1][1]+vec[i].b);
if(i>=3 && vec[i].w-vec[i-2].w<=d)
dp[i][0]=min(dp[i][0],dp[i-2][1]+vec[i].b+vec[i-1].a);
dp[i][1]=min(dp[i][1],dp[i-1][0]+vec[i].b);
}
return dp[n][0];
}
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();
n = A.size();
for(int i=1;i<=n;i++)
{
vec[i].a=A[i-1];
vec[i].b=B[i-1];
vec[i].w=W[i-1];
}
sort(vec+1,vec+n+1,cmp);
vector<long long>rasp;
for(int i=0;i<q;i++)
{
rasp.push_back(solve(E[i]));
}
return rasp;
}
