#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e17;
struct item{
int w;
int a,b;
inline friend bool operator < (item fr,item sc){
return fr.w<sc.w;
}
};
int n;
item a[MAXN];
long long pref[MAXN];
long long sum(int l,int r){
return pref[r]-pref[l-1];
}
long long dp[MAXN];
long long calcdp(int delta){
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]+a[i].a;
for(int f=i-1;f>=1;f--){
if(a[i].w-a[f].w>delta)break;
dp[i]=min(dp[i],dp[f-1]+a[i].b+a[f].b+sum(f+1,i-1));
}
}
return dp[n];
}
vector<long long> calculate_costs(vector<int> W, vector<int> A,vector<int> B,vector<int> E){
n=int(W.size());
for(int i=1;i<=n;i++){
a[i]={W[i-1],A[i-1],B[i-1]};
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
pref[i]=pref[i-1]+a[i].a;
}
vector<long long> ans;
for(int i:E){
ans.push_back(calcdp(i));
}
return ans;
}
/*int main(){
auto res=calculate_costs({15, 12, 2, 10, 21},
{5, 4, 5, 6, 3},
{1, 2, 2, 3, 2},
{5, 9, 1});
for(auto s:res)cout<<s<<" ";
return 0;
}*/
