#include "nile.h"
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define mp make_pair
using namespace std;
int n;
int curr=0;
struct node{
int ans;
int even;
int evenskip;
int odd;
int oddskip;
int size;
void operator+(node a){
curr-=this->ans;
curr-=a.ans;
if(this->size==1){
this->even=min(this->even,a.odd);
this->odd=min(this->odd,a.even);
this->evenskip=min(this->evenskip,a.oddskip);
this->oddskip=min(this->oddskip,a.evenskip);
}else{
this->even=min(this->even,a.even);
this->odd=min(this->odd,a.odd);
this->evenskip=min(this->evenskip,a.evenskip);
this->oddskip=min(this->oddskip,a.oddskip);
}
this->size+=a.size;
this->size%=2;
if(this->size==0)ans=0;
else{
ans=min(this->odd,this->evenskip);
}
curr+=this->ans;
return;
}
};
struct dsu{
vector<int>parent;
vector<int>vals;
vector<node>v;
dsu(vector<pair<int,pair<int,int>>>&artifact){
parent.resize(n);
vals.resize(n);
for(int i=0;i<n;i++)parent[i]=i;
v.resize(n);
for(int i=0;i<n;i++){
curr+=artifact[i].second.second;
int val=artifact[i].second.second-artifact[i].second.first;
vals[i]=val;
v[i].ans=val;
v[i].odd=val;
v[i].size=1;
v[i].even=LLONG_MAX;
v[i].evenskip=LLONG_MAX;
v[i].oddskip=LLONG_MAX;
}
}
int query(int a){
if(parent[a]==a){
return a;
}
return parent[a]=query(parent[a]);
}
void merge(int a,int b){
int ff=query(a),ss=query(b);
if(ff==ss)return;
if(ff<ss){
parent[ss]=ff;
v[ff]+v[ss];
}else{
parent[ff]=ss;
v[ss]+v[ff];
}
}
void update(int idx){
int par=query(idx);
curr-=v[par].ans;
int broj=idx-par+1;
broj%=2;
if(broj==0){
v[par].evenskip=min(v[par].evenskip,vals[idx]);
}else{
v[par].oddskip=min(v[par].oddskip,vals[idx]);
}
v[par].ans=min(v[par].odd,v[par].evenskip);
if(v[par].size==0LL)v[par].ans=0LL;
curr+=v[par].ans;
}
};
vector<int> calculate_costs(vector<signed> W, vector<signed> A,vector<signed> B, vector<signed> E) {
n=A.size();
vector<pair<int,pair<int,int>>>artifact(n);
for(int i=0;i<n;i++){
artifact[i].first=W[i];
artifact[i].second.first=B[i];
artifact[i].second.second=A[i];
}
sort(artifact.begin(),artifact.end());
dsu solution(artifact);
priority_queue<pair<int,pair<int,int>>>q;
for(int i=0;i<n-1;i++){
q.push(mp(-(artifact[i+1].first-artifact[i].first),mp(i,i+1)));
}
for(int i=0;i<n-2;i++){
q.push(mp(-(artifact[i+2].first-artifact[i].first),mp(i,i+2)));
}
vector<pair<int,int>>nums;
vector<int>answers;
nums.push_back(mp(0LL,0LL));
answers.push_back(curr);
while(!q.empty()){
pair<int,pair<int,int>>p=q.top();
q.pop();
p.first*=(-1);
nums.push_back(mp(p.first,nums.size()));
if(p.second.second-p.second.first==1){
solution.merge(p.second.first,p.second.second);
}else{
solution.update(p.second.first+1);
}
answers.push_back(curr);
}
signed Q = (signed)E.size();
vector<int> R(Q);
for(int i=0;i<Q;i++){
int c=E[i];
auto it=upper_bound(nums.begin(),nums.end(),mp(c+1,-1LL));
it--;
pair<int,int>p=*it;
R[i]=answers[p.second];
}
return R;
}
