#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
return a.w<b.w;
}
int lr[MAXN];
long long sufs[MAXN];
long long dp[MAXN];
long long mnn,seg[4*MAXN];
void Initialise(int ind, int l, int r)
{
seg[ind]=LONG_LONG_MAX;
if (l==r)
{
return;
}
int mid=(l+r)/2;
Initialise(ind*2,l,mid);
Initialise(ind*2+1,mid+1,r);
}
void Update(int ind, int l, int r, int pos, long long st)
{
if (l==r)
{
seg[ind]=st;
return;
}
int mid=(l+r)/2;
if (pos<=mid) Update(ind*2,l,mid,pos,st);
else Update(ind*2+1,mid+1,r,pos,st);
seg[ind]=min(seg[ind*2],seg[ind*2+1]);
}
void Query(int ind, int l, int r, int ql, int qr)
{
if (ql<=l && qr>=r)
{
mnn=min(mnn,seg[ind]);
return;
}
int mid=(l+r)/2;
if (ql<=mid) Query(ind*2,l,mid,ql,qr);
if (qr>=mid+1) Query(ind*2+1,mid+1,r,ql,qr);
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
int Q = (int)E.size();
n=A.size();
for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
sort(ar,ar+n,cmp);
vector<long long> R(Q);
for (int curq=0;curq<Q;curq++)
{
int d=E[curq];
lr[0]=0;
for (int q=1;q<n;q++)
{
lr[q]=lr[q-1];
while ((ar[q].w-ar[lr[q]].w)>d) lr[q]++;
}
sufs[n]=0;
sufs[n-1]=ar[n-1].a;
for (int q=n-2;q>=0;q--) sufs[q]=sufs[q+1]+ar[q].a;
Initialise(1,0,n);
dp[0]=0;
Update(1,0,n,0,dp[0]+ar[0].b+sufs[1]);
dp[1]=ar[0].a;
Update(1,0,n,1,dp[1]+ar[1].b+sufs[2]);
for (int q=2;q<=n;q++) ///
{
dp[q]=dp[q-1]+ar[q-1].a;
if (lr[q-1]!=q-1)
{
mnn=LONG_LONG_MAX;
Query(1,0,n,lr[q-1],q-2);
mnn-=sufs[q-1];
mnn+=ar[q-1].b;
//cout<<q<<" "<<mnn<<" xx\n";
if (mnn<dp[q]) dp[q]=mnn;
}
Update(1,0,n,q,dp[q]+ar[q].b+sufs[q+1]);
/*long long buf=0;
for (int w=q-2;w>=0;w--)
{
if ((ar[q-1].w-ar[w].w)>d) break;
long long cur=dp[w]+(ar[q-1].b)+ar[w].b+buf;
if (cur<dp[q]) dp[q]=cur;
buf+=ar[w].a;
}*/
//cout<<dp[q]<<" t ";
}
//cout<<"\n";
R[curq]=dp[n];
}
return R;
}
