#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct segtree{
int n;
vector<int>tree;
segtree(int n,vector<int>&v):n(n),tree(2*n){
for(int i=n;i<2*n;i++){
tree[i]=v[i-n];
}
for(int i=n-1;i>0;i--){
tree[i]=min(tree[2*i],tree[2*i+1]);
}
}
void update(int pos,int val){
tree[pos+=n]=val;
for(pos/=2;pos>0;pos/=2){
tree[pos]=min(tree[2*pos],tree[2*pos+1]);
}
}
int query(int l,int r){
int ans=2e9;
for(l+=n,r+=n;l<r;l/=2,r/=2){
if(l%2)ans=min(ans,tree[l++]);
if(r%2)ans=min(ans,tree[--r]);
}
return ans;
}
};
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
int n=W.size(),q=E.size();
vector<ll>res(q);
ll ans=0;
for(int i:A)ans+=i;
vector<pair<int,int>>a(n);
for(int i=0;i<n;i++){
a[i]={W[i],A[i]-B[i]};
}
sort(a.begin(),a.end());
vector<pair<int,int>>diff(n-1);
for(int i=0;i<n-1;i++){
diff[i]={a[i+1].first-a[i].first,i};
}
sort(diff.begin(),diff.end());
reverse(diff.begin(),diff.end());
vector<pair<int,int>>diff2(n-2);
for(int i=0;i<n-2;i++){
diff2[i]={a[i+2].first-a[i].first,i};
}
sort(diff2.begin(),diff2.end());
reverse(diff2.begin(),diff2.end());
vector<int>v1(n,2e9),v2(n,2e9);
for(int i=0;i<n;i++){
if(i%2){
v1[i]=a[i].second;
}else{
v2[i]=a[i].second;
}
}
segtree seg1(n,v1),seg2(n,v2);
vector<pair<int,int>>e(q);
for(int i=0;i<q;i++){
e[i]={E[i],i};
}
sort(e.begin(),e.end());
set<int>s;
for(int i=0;i<=n;i++)s.insert(i);
for(int _=0;_<q;_++){
int d=e[_].first;
vector<int>update;
while(!diff.empty()&&diff.back().first<=d){
auto it=s.upper_bound(diff.back().second);
it--;
diff.pop_back();
update.push_back(*it);
if((*next(it)-*it)%2){
if(*it%2){
ans-=seg1.query(*it,*next(it));
}else{
ans-=seg2.query(*it,*next(it));
}
}
if((*next(next(it))-*next(it))%2){
if(*next(it)%2){
ans-=seg1.query(*next(it),*next(next(it)));
}else{
ans-=seg2.query(*next(it),*next(next(it)));
}
}
if((*next(next(it))-*it)%2){
if(*it%2){
ans+=seg1.query(*it,*next(next(it)));
}else{
ans+=seg2.query(*it,*next(next(it)));
}
}
s.erase(next(it));
}
while(!diff2.empty()&&diff2.back().first<=d){
pair<int,int>p=diff2.back();
diff2.pop_back();
auto it=s.upper_bound(p.second+1);
it--;
if((*next(it)-*it)%2){
if(*it%2){
ans-=seg1.query(*it,*next(it));
}else{
ans-=seg2.query(*it,*next(it));
}
}
if(p.second%2){
seg1.update(p.second+1,a[p.second+1].second);
}else{
seg2.update(p.second+1,a[p.second+1].second);
}
if((*next(it)-*it)%2){
if(*it%2){
ans+=seg1.query(*it,*next(it));
}else{
ans+=seg2.query(*it,*next(it));
}
}
}
res[e[_].second]=ans;
}
return res;
}
