#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=1e5+5, inf=1e18;
ll n, q, dsu[nx], cur;
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
struct Info
{
ll w, a, b;
bool operator< (const Info &o) const {return w<o.w;}
Info(ll w=0, ll a=0, ll b=0): w(w), a(a), b(b) {}
} info[nx];
struct Group
{
ll smb, l, r;
ll min_odd, min_even, min_pos;
Group(int idx=0) {
smb=info[idx].b;
l=r=idx;
min_odd=min_even=min_pos=inf;
if (idx%2) min_odd=info[idx].a-info[idx].b;
else min_even=info[idx].a-info[idx].b;
}
void merge(Group o)
{
r=o.r;
smb+=o.smb;
min_odd=min(min_odd, o.min_odd);
min_even=min(min_even, o.min_even);
min_pos=min(min_pos, o.min_pos);
}
ll value()
{
int sz=(r-l+1);
if (sz%2==0) return smb;
if (l%2) return smb+min(min_odd, min_pos);
else return smb+min(min_even, min_pos);
}
} g[nx];
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();
q=E.size();
for (int i=0; i<n; i++) dsu[i]=i, info[i]=Info(W[i], A[i], B[i]);
sort(info, info+n);
for (int i=0; i<n; i++) g[i]=Group(i), cur+=g[i].value();
vector<tuple<ll, ll, ll>> srt; // {value, type, index} 0->{i, i+1}, 1->{i-1, i+1}, 2->query
for (int i=1; i<n; i++) srt.push_back({info[i].w-info[i-1].w, 0, i-1});
for (int i=1; i<n-1; i++) srt.push_back({info[i+1].w-info[i-1].w, 1, i});
for (int i=0; i<q; i++) srt.push_back({E[i], 2, i});
sort(srt.begin(), srt.end());
vector<ll> res(q);
for (auto [_, t, idx]:srt)
{
if (t==0)
{
cur-=g[find(idx)].value();
cur-=g[find(idx+1)].value();
g[find(idx)].merge(g[find(idx+1)]);
dsu[find(idx+1)]=dsu[find(idx)];
cur+=g[find(idx)].value();
}
else if (t==1)
{
cur-=g[find(idx)].value();
g[find(idx)].min_pos=min(g[find(idx)].min_pos, info[idx].a-info[idx].b);
cur+=g[find(idx)].value();
}
else res[idx]=cur;
}
return res;
}
