#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1<<18;
const ll INF=1e18;
ll parent[MAXN], rli[MAXN];
vector<ll> seg1(2*MAXN,INF), seg2(2*MAXN,INF);
vector<pair<ll,ll>> E2, sli;
vector<pair<ll,ll>> l, l2; // l은 답 저장용, l2는 구간 차이 저장용
vector<ll> ansli(MAXN), ansli2(MAXN), ansli3(MAXN), ansli4(MAXN, 1), ansli5(MAXN);
// 각 구간에서 시작하는 답 저장하기. ansli:구간합, ansli2:구간 짝수 인덱스 최소, ansli3: 구간 홀수 인덱스 최소
// ansli4: 짝수 구간인가 홀수 구간인가?
ll findp(ll a){
if(a==parent[a]) return a;
return parent[a]=findp(parent[a]);
}
void uni(ll a, ll b){
ll a2=findp(a);
ll b2=findp(b);
if(a2==b2) return;
if(a2>b2) swap(a2,b2);
parent[b2]=a2;
rli[a2]=max(rli[b2],rli[a2]);
}
ll query(ll node, ll s, ll e, ll l, ll r){
if(e<l || s>r) return INF;
if(l<=s || e<=r){
if(l%2==0) return seg1[node];
else return seg2[node];
}
ll mid=(s+e)>>1;
return min(query(2*node,s,mid,l,r),query(2*node+1,mid+1,e,l,r));
}
void update(ll node, ll s, ll e, ll idx, ll x){
if(idx<s || idx>e) return;
if(s==e){
if(idx%2==0) seg1[node]=x;
else seg2[node]=x;
return;
}
ll mid=(s+e)>>1;
update(2*node,s,mid,idx,x);
update(2*node+1,mid+1,e,idx,x);
seg1[node]=min(seg1[node*2],seg1[node*2+1]);
seg2[node]=min(seg2[node*2],seg2[node*2+1]);
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
ll N = (int)W.size();
ll Q = (int)E.size();
for(ll i=0;i<N;i++) rli[i]=parent[i]=i;
ll ans=0;
for(ll i=0;i<N;i++) ans+=A[i];
for(ll i=0;i<N;i++) {
l.push_back({W[i],A[i]-B[i]});
}
sort(l.begin(),l.end());
for(ll i=0;i<N;i++){
ansli[i]=ansli2[i]=l[i].second;
ansli3[i]=INF;
if(i>0 && i<N-1){
sli.push_back({l[i+1].first-l[i-1].first,i});
}
}
for(ll i=0;i<N-1;i++) l2.push_back({l[i+1].first-l[i].first,i});
sort(l2.begin(),l2.end());
vector<ll> R(Q, 0);
for(ll i=0;i<Q;i++) E2.push_back({E[i],i});
sort(E2.begin(),E2.end());
sort(sli.begin(),sli.end());
ll ne=0;
ll j=0;
ll k=0;
for(ll i=0;i<Q;i++){
while(k<N-2 && sli[k].first<=E2[i].first){
update(1,0,MAXN-1,sli[k].second,l[sli[k].second].second);
k++;
}
while(j<N-1 && l2[j].first<=E2[i].first){
ll p1=findp(l2[j].second), p2=findp(l2[j].second+1);
ans+=ansli5[p1];
ans+=ansli5[p2];
uni(l2[j].second,l2[j].second+1); // 병합할 때 끝 인덱스도 같이 관리해야 한다.
ll p3=findp(l2[j].second);
ll l=p3, r=rli[p3];
if(ansli4[p1]==0){//앞에가 짝수였다면
ansli2[p3]=min(ansli2[p1],ansli2[p2]);
ansli3[p3]=min(ansli3[p1],ansli3[p2]);
}
else{
ansli2[p3]=min(ansli2[p1],ansli3[p2]);
ansli3[p3]=min(ansli3[p1],ansli2[p2]);
}
ansli[p3]=ansli[p1]+ansli[p2];
if((r-l)%2==1) ansli4[p3]=0;
else ansli4[p3]=1;
ansli5[p3]=ansli[p3]-min(ansli2[p3],query(1,0,MAXN-1,l+1,r-1))*ansli4[p3];
ans-=ansli5[p3];
j+=1;
}
R[E2[i].second]=ans;
ne=E2[i].first;
}
return R;
}
