#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
#define ull unsigned long long
#define ld long double
#define ll long long
// #define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e5 + 50, K = 22;
// #include "nile.h"
ll n;
ll sum = 0;
vector<ll> c;
vector<pair<ll, ll>> q;
struct dsu{
vector<ll> sz, p, minodd, mineven, minidx, altmin;
ll tot = 0;
dsu(int n){
sz = p = minodd = mineven = minidx = altmin = vector<ll> (n + 5, 0ll);
for(int i = 0; i < n; i++){
sz[i] = 1, p[i] = i, minidx[i] = i, tot += c[i];
minodd[i] = mineven[i] = altmin[i] = inf;
if(i % 2)
minodd[i] = c[i];
else
mineven[i] = c[i];
}
}
ll find(ll u){
return p[u] == u ? u : p[u] = find(p[u]);
}
ll cost(ll u){
if(sz[u] % 2 == 0)
return 0;
if(minidx[u] % 2)
return min(minodd[u], altmin[u]);
return min(mineven[u], altmin[u]);
}
bool merge(int a, int b){
int idx = (a + b) / 2;
a = find(a);
b = find(b);
if(a == b){
tot -= cost(a);
altmin[a] = min(altmin[a], c[idx]);
tot += cost(a);
return false;
}
tot -= cost(a);
tot -= cost(b);
if(sz[a] < sz[b])
swap(a, b);
minodd[a] = min(minodd[a], minodd[b]);
mineven[a] = min(mineven[a], mineven[b]);
minidx[a] = min(minidx[a], minidx[b]);
altmin[a] = min(altmin[a], altmin[b]);
sz[a] += sz[b];
p[b] = a;
tot += cost(a);
return true;
}
};
struct item{
ll w, a, b;
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
n = a.size();
c = vector<ll> (n, 0ll);
vector<ll> ans((ll)e.size());
for(auto i : b)
sum += i;
vector<item> arr(n);
for(int i = 0; i < n; i++)
arr[i] = {w[i], a[i], b[i]};
sort(all(arr), [](item x, item y){
return x.w < y.w;
});
for(int i = 0; i < n; i++)
c[i] = arr[i].a - arr[i].b;
for(int i = 0; i < e.size(); i++)
q.push_back({e[i], i});
sort(all(q));
vector<pii> p;
for(int i = 0; i < n - 1; i++){
p.push_back({i, i + 1});
if(i + 2 < n)
p.push_back({i, i + 2});
}
sort(all(p), [&](pii x, pii y){
return arr[x.second].w - arr[x.first].w < arr[y.second].w - arr[y.first].w;
});
dsu ds(n);
int i = 0;
for(auto [d, idx] : q){
while(i < p.size() && arr[p[i].second].w - arr[p[i].first].w <= d){
ds.merge(p[i].first, p[i].second);
i++;
}
ans[idx] = sum + ds.tot;
}
return ans;
}
