#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
#include<set>
#include "nile.h"
using namespace std;
const int MAX_N=1e5+5;
long long a[MAX_N];
long long b[MAX_N];
int w[MAX_N];
int n;
vector<int>v;
int d;
long long dp[MAX_N];
long long solve()
{
for(int i=1;i<=v.size();i++)
{
int id=v[i-1];
dp[i]=dp[i-1]+a[id];
if(i>=2)
{
dp[i]=min(dp[i],dp[i-2]+b[id]+b[v[i-2]]);
}
if(i>=3)
{
if(w[id]-w[v[i-3]]<=d)
{
dp[i]=min(dp[i],dp[i-3]+b[id]+a[v[i-2]]+b[v[i-3]]);
}
}
}
return dp[v.size()];
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
n=W.size();
vector<pair<int,int>>order;
for(int i=0;i<n;i++)
{
a[i]=A[i];
b[i]=B[i];
w[i]=W[i];
order.push_back({w[i],i});
}
sort(order.begin(),order.end());
vector<pair<int,int>>gaps;
for(int i=1;i<n;i++)
{
gaps.push_back({order[i].first-order[i-1].first,i-1});
}
sort(gaps.begin(),gaps.end());
vector<long long>answers;
answers.resize((int)(E.size()));
vector<pair<int,int>>queries;
for(int i=0;i<E.size();i++)
{
queries.push_back({E[i],i});
}
sort(queries.begin(),queries.end());
int idgap=0;
set<int>posgap;
long long ans;
for(int idquery=0;idquery<queries.size();idquery++)
{
d=queries[idquery].first;
if(0 && idquery>0)
{
while(idgap<gaps.size() && gaps[idgap].first<=d)
{
posgap.erase(gaps[idgap].second);
int prv,nxt;
auto it=posgap.upper_bound(gaps[idgap].second);
nxt=(*it);
it--;
prv=(*it);
int lenprv=gaps[idgap].second-prv;
int lennxt=nxt-gaps[idgap].second;
ans-=lenprv%2;ans-=lennxt%2;
ans+=(nxt-prv)%2;
idgap++;
}
answers[queries[idquery].second]=ans;
continue;
}
while(idgap<gaps.size() && gaps[idgap].first<=d)
{
idgap++;
}
for(int j=idgap;j<gaps.size();j++)
{
posgap.insert(gaps[j].second);
}
posgap.insert(-2);
posgap.insert(n-1);
ans=0;
v.clear();
v.push_back(order[0].second);
for(int i=1;i<n;i++)
{
if(order[i].first-order[i-1].first>d)
{
ans+=solve();
v.clear();
}
v.push_back(order[i].second);
}
ans+=solve();
answers[queries[idquery].second]=ans;
}
return answers;
}
