#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e9;
const int MN = 1e5+5;
int par[MN], sz[MN], compL[MN], compR[MN];
ll minEven[MN], minOdd[MN], minAll[MN], compAns[MN], sumB[MN], minJump[MN];
int n, q;
vector<int> a, b, w;
ll tot;
void init_dsu() {
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
minEven[i] = INF;
minOdd[i] = a[i] - b[i];
minAll[i] = a[i] - b[i];
compL[i] = compR[i] = i;
compAns[i] = a[i];
tot += a[i];
sumB[i] = b[i];
minJump[i] = INF;
}
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
tot -= compAns[u];
tot -= compAns[v];
ll minEven2, minOdd2, minAll2;
minEven2 = minEven[u];
minOdd2 = minOdd[u];
if ((compR[u] - compL[u] + 1) & 1) {
minEven2 = min(minEven2, minOdd[v]);
minOdd2 = min(minOdd2, minEven[v]);
}
else {
minEven2 = min(minEven2, minEven[v]);
minOdd2 = min(minOdd2, minOdd[v]);
}
minAll2 = min({minOdd2, minAll[u], minJump[v]});
if (sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
compL[v] = min(compL[v], compL[u]);
compR[v] = max(compR[v], compR[u]);
minEven[v] = minEven2;
minOdd[v] = minOdd2;
minAll[v] = minAll2;
sumB[v] += sumB[u];
minJump[v] = min(minJump[v], minJump[u]);
compAns[v] = sumB[v];
if ((compR[v] - compL[v] + 1) & 1) compAns[v] += minAll[v];
tot += compAns[v];
}
void combine_over(int idx) {
int v = find(idx);
minAll[v] = min(minAll[v], (ll)(a[idx+1] - b[idx+1]));
tot -= compAns[v];
compAns[v] = sumB[v];
if ((compR[v] - compL[v] + 1) & 1) compAns[v] += minAll[v];
tot += compAns[v];
minJump[v] = min(minJump[v], (ll)(a[idx+1] - b[idx+1]));
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
a = A;
b = B;
w = W;
n = a.size();
q = E.size();
vector<tuple<int, int, int>> arr;
for (int i = 0; i < n; i++) {
arr.push_back({w[i], a[i], b[i]});
}
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++) {
w[i] = get<0>(arr[i]);
a[i] = get<1>(arr[i]);
b[i] = get<2>(arr[i]);
}
tot = 0;
init_dsu();
vector<pair<int, int>> qr;
for (int i = 0; i < q; i++) {
qr.push_back({E[i], i});
}
sort(qr.begin(), qr.end());
vector<pair<int, int>> diff;
for (int i = 0; i < n-1; i++) {
diff.push_back({w[i+1] - w[i], i});
}
sort(diff.rbegin(), diff.rend());
vector<pair<int, int>> diff2;
for (int i = 0; i < n-2; i++) {
diff2.push_back({w[i+2] - w[i], i});
}
sort(diff2.rbegin(), diff2.rend());
vector<ll> ans(q);
for (auto [d, idx]: qr) {
while (!diff.empty() && diff.back().first <= d) {
int id = diff.back().second;
diff.pop_back();
merge(id, id+1);
}
while (!diff2.empty() && diff2.back().first <= d) {
int id = diff2.back().second;
diff2.pop_back();
combine_over(id);
}
ans[idx] = tot;
}
return ans;
}
/*
ll get_ans(int d) {
ll tot = 0;
ll minDiff = INF;
int cnt = 0;
ll curr = 0;
for (int i = 0; i < n; i++) {
if (i > 0 && abs(w[i] - w[i-1]) > d) {
tot += curr;
if (cnt & 1) tot += minDiff;
curr = cnt = 0;
minDiff = INF;
}
cnt++;
curr += b[i];
if ((cnt & 1) || (i > 0 && i < n && w[i+1] - w[i-1] <= d)) {
minDiff = min(minDiff, (ll)(a[i] - b[i]));
}
}
tot += curr;
if (cnt & 1) tot += minDiff;
return tot;
}*/
