#include <bits/stdc++.h>
#include "nile.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 1e5 + 7, ofs = (1 << 17), inf = 1e9;
ll cur;
int par[N], siz[N], sol[N][2];
int t[2*ofs];
void add(int x, int y) {
x += ofs;
t[x] = y;
while (x /= 2) t[x] = min(t[2*x], t[2*x+1]);
}
int query(int x, int a, int b, int lo = 0, int hi = ofs-1) {
if (b < lo || hi < a) return inf;
if (a <= lo && hi <= b) return t[x];
int mid = (lo + hi) / 2;
return min(query(2*x, a, b, lo, mid), query(2*x+1, a, b, mid+1, hi));
}
inline ll cost(int x) {return (siz[x] % 2 == 0) ? 0 : min(query(1, x, x+siz[x]-1), sol[x][x%2]);}
int find(int x) {return (x == par[x]) ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (x > y) swap(x, y);
cur -= cost(x)+cost(y);
par[y] = x;
siz[x] += siz[y];
for (int i = 0; i < 2; i++) sol[x][i] = min(sol[x][i], sol[y][i]);
cur += cost(x);
}
vector <ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size(), q = E.size();
fill(t, t+2*ofs, inf);
ll res = 0;
for (int i = 0; i < n; i++) res += B[i], A[i] -= B[i], cur += A[i];
vector <pii> tmp;
for (int i = 0; i < n; i++) tmp.pb({W[i], A[i]});
sort(all(tmp));
for (int i = 0; i < n; i++) W[i] = tmp[i].F, A[i] = tmp[i].S;
for (int i = 0; i < n; i++) par[i] = i, siz[i] = 1, sol[i][i%2] = A[i], sol[i][i%2==0] = inf;
vector <pair <pii, int> > v;
for (int j = 0; j < 2; j++) for (int i = 0; i < n-j-1; i++) v.pb({{W[i+j+1]-W[i], j}, i});
for (int i = 0; i < q; i++) v.pb({{E[i], 2}, i});
sort(all(v));
vector <ll> ans(q);
for (auto it : v) {
int x = it.S;
if (!it.F.S) unite(x, x+1);
else if (it.F.S == 1) {
cur -= cost(find(x));
add(x+1, A[x+1]);
cur += cost(find(x));
}
else ans[x] = res+cur;
}
return ans;
}
