#include "nile.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<int> parent;
vector<int> sz;
vector<int> mnDEF;
vector<pair<int,pair<int,int>>> _a;
vector<int> mnEV;
vector<int> mnUV;
vector<pair<int,int>> mnBORDER;
vector<int> mn;
int sm=0;
int getParent(int x){
if(parent[x]==x) return x;
return parent[x]=getParent(parent[x]);
}
void unite(int a, int b){
a=getParent(a); b=getParent(b);
if(a==b) return;
parent[b]=a;
if(sz[a]%2) sm-=mn[a];
if(sz[b]%2) sm-=mn[b];
if(sz[a]%2){
mnEV[a]=min(mnEV[a], mnUV[b]);
mnUV[a]=min(mnUV[a], mnEV[b]);
}else{
mnEV[a]=min(mnEV[a], mnEV[b]);
mnUV[a]=min(mnUV[a], mnUV[b]);
}
mnBORDER[a].second=mnBORDER[b].second;
sz[a]+=sz[b];
mnDEF[a]=min(mnDEF[a],mnDEF[b]);
mn[a]=min(mnDEF[a],min(mnEV[a],min(mnBORDER[a].first,mnBORDER[a].second)));
if(sz[a]%2) sm+=mn[a];
}
void addMN(int x){
int p=getParent(x);
mnDEF[p]=min(mnDEF[p],(_a[x].second.first-_a[x].second.second));
if(sz[p]%2) sm-=mn[p];
mn[p]=min(mn[p],mnDEF[p]);
if(sz[p]%2) sm+=mn[p];
}
std::vector<int> calculate_costs(std::vector<signed> W, std::vector<signed> A, std::vector<signed> B, std::vector<signed> E) {
int q = sz(E);
int n=sz(W);
mn.resize(n,1e17); sz.resize(n); parent.resize(n);
mnDEF.resize(n,1e17);
mnEV.resize(n,1e17);
mnUV.resize(n,1e17);
mnBORDER.resize(n,{1e17,1e17});
vector<pair<int,int>> e(q);
_a.resize(n);
for (int i = 0; i < q; i++) e[i]={E[i],i};
for (int i = 0; i < n; i++) _a[i]={W[i],{A[i],B[i]}};
sort(all(_a));
sort(all(e));
vector<pair<int,int>> df(n-1);
vector<pair<int,int>> df2(n-2);
for (int i = 0; i < n-1; i++) df[i]={_a[i+1].first-_a[i].first,i};
for (int i = 0; i < n-2; i++) df2[i]={_a[i+2].first-_a[i].first,i};
sm=0;
for (int i = 0; i < n; i++)
{
sm+=_a[i].second.first;
sz[i]=1;
parent[i]=i;
mn[i]=_a[i].second.first-_a[i].second.second;
mnEV[i]=_a[i].second.first-_a[i].second.second;
mnBORDER[i]={_a[i].second.first-_a[i].second.second,_a[i].second.first-_a[i].second.second};
}
sort(all(df));
sort(all(df2));
std::vector<int> R(q, 0);
int j=0;
int j2=0;
for (int i = 0; i < q; i++)
{
while(j<n-1){
if(df[j].first>e[i].first) break;
unite(df[j].second,df[j].second+1);
j++;
}
while(j2<n-2){
if(df2[j2].first>e[i].first) break;
addMN(df2[j2].second+1);
j2++;
}
R[e[i].second]=sm;
}
return R;
}
