#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
int n;
vector<int> p, sz, l;
vector<ll> mn0, mn1, mn2;
DSU(int n, const vector<ll>& C): n(n) {
p.resize(n);
sz.assign(n, 1);
l.resize(n);
mn0.resize(n);
mn1.assign(n, (ll)4e18);
mn2.assign(n, (ll)4e18);
for (int i = 0; i < n; i++) {
p[i] = i;
l[i] = i;
mn0[i] = C[i];
}
}
int find(int x){
while(p[x] != x){
p[x] = p[p[x]];
x = p[x];
}
return x;
}
ll contrib(int r){
if(sz[r] & 1) return min(mn0[r], mn2[r]);
return 0;
}
void unite_adj(int a, int b, ll &extra){
int ra = find(a), rb = find(b);
if(ra == rb) return;
if(l[ra] > l[rb]) swap(ra, rb);
extra -= contrib(ra);
extra -= contrib(rb);
ll ne, no;
if((sz[ra] & 1) == 0){
ne = min(mn0[ra], mn0[rb]);
no = min(mn1[ra], mn1[rb]);
} else {
ne = min(mn0[ra], mn1[rb]);
no = min(mn1[ra], mn0[rb]);
}
ll nt = min(mn2[ra], mn2[rb]);
p[rb] = ra;
sz[ra] += sz[rb];
mn0[ra] = ne;
mn1[ra] = no;
mn2[ra] = nt;
extra += contrib(ra);
}
void enable_mid(int idx, ll val, ll &extra){
int r = find(idx);
ll old = contrib(r);
mn2[r] = min(mn2[r], val);
ll nw = contrib(r);
extra += (nw - old);
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int N = (int)W.size();
int Q = (int)E.size();
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j){
return W[i] < W[j];
});
vector<ll> w(N), c(N);
ll base = 0;
for(int i = 0; i < N; i++){
int id = ord[i];
w[i] = W[id];
c[i] = (ll)A[id] - (ll)B[id];
base += (ll)B[id];
}
struct Ev { ll d; int t; int i; };
vector<Ev> ev;
ev.reserve(2*N);
for(int i = 0; i + 1 < N; i++){
ev.push_back({w[i+1] - w[i], 0, i});
}
for(int i = 0; i + 2 < N; i++){
ev.push_back({w[i+2] - w[i], 1, i});
}
sort(ev.begin(), ev.end(), [&](const Ev& a, const Ev& b){
if(a.d != b.d) return a.d < b.d;
return a.t < b.t;
});
vector<int> qord(Q);
iota(qord.begin(), qord.end(), 0);
sort(qord.begin(), qord.end(), [&](int i, int j){
return E[i] < E[j];
});
DSU dsu(N, c);
ll extra = 0;
for(int i = 0; i < N; i++) extra += c[i];
vector<ll> ans(Q);
int p = 0;
for(int qi : qord){
int D = E[qi];
while(p < (int)ev.size() && ev[p].d <= D){
if(ev[p].t == 0){
int i = ev[p].i;
dsu.unite_adj(i, i+1, extra);
} else {
int i = ev[p].i;
int mid = i + 1;
dsu.enable_mid(mid, c[mid], extra);
}
p++;
}
ans[qi] = base + extra;
}
return ans;
}
