#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz, mn;
vector<ll> evenv, oddv, twov;
DSU(int n, vector<ll>& C) {
p.resize(n);
sz.assign(n, 1);
mn.resize(n);
evenv.resize(n);
oddv.assign(n, LLONG_MAX);
twov.assign(n, LLONG_MAX);
for (int i = 0; i < n; i++) {
p[i] = i;
mn[i] = i;
evenv[i] = C[i];
}
}
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
ll cost(int x) {
if (sz[x] & 1) return min(evenv[x], twov[x]);
return 0;
}
void merge(int a, int b, ll &cur) {
a = find(a);
b = find(b);
if (a == b) return;
if (mn[a] > mn[b]) swap(a, b);
cur -= cost(a);
cur -= cost(b);
ll ne = min(evenv[a], (sz[a] & 1) ? oddv[b] : evenv[b]);
ll no = min(oddv[a], (sz[a] & 1) ? evenv[b] : oddv[b]);
ll nt = min(twov[a], twov[b]);
p[b] = a;
sz[a] += sz[b];
evenv[a] = ne;
oddv[a] = no;
twov[a] = nt;
cur += cost(a);
}
void enable(int x, vector<ll>& C, ll &cur) {
x = find(x);
if (sz[x] & 1) {
ll old = min(evenv[x], twov[x]);
twov[x] = min(twov[x], C[mn[x] + 1]);
ll nw = min(evenv[x], twov[x]);
cur += nw - old;
} else {
twov[x] = min(twov[x], C[mn[x] + 1]);
}
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size(), q = E.size();
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int a, int b){ return W[a] < W[b]; });
vector<ll> w(n), c(n);
ll base = 0;
for (int i = 0; i < n; i++) {
w[i] = W[id[i]];
c[i] = (ll)A[id[i]] - B[id[i]];
base += B[id[i]];
}
struct Edge { ll d; int t, i; };
vector<Edge> ev;
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(), [](auto &a, auto &b){ return a.d < b.d; });
vector<int> ord(q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b){ return E[a] < E[b]; });
DSU dsu(n, c);
ll cur = 0;
for (int i = 0; i < n; i++) cur += c[i];
vector<ll> ans(q);
int p = 0;
for (int qi : ord) {
while (p < (int)ev.size() && ev[p].d <= E[qi]) {
if (ev[p].t == 0) dsu.merge(ev[p].i, ev[p].i + 1, cur);
else dsu.enable(ev[p].i, c, cur);
p++;
}
ans[qi] = base + cur;
}
return ans;
}
