#include <bits/stdc++.h>
//#include "nile.h"
#define ld long double
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define in insert
#define arr(x) array <int, x>
#define vvec vector<vector<int>>
#define Keiiiii ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ___ 1000 * clock() / CLOCKS_PER_SEC
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int n, q;
long long res, s[N];
int p[N], L[N], R[N];
vector <pii> ee;
arr(3) a[N];
pii t[N];
struct ST
{
int st[N * 4];
void up(int i, int l, int r, int x, int y)
{
if(x > r || x < l) return;
if(l == r) { st[i] = y; return; }
int mid = (l + r) >> 1;
up(i << 1, l, mid, x, y);
up(i << 1 | 1, mid + 1, r, x, y);
st[i] = min(st[i << 1], st[i << 1 | 1]);
}
int get(int i, int l, int r, int x, int y)
{
if(x > r || y < l) return inf;
if(x <= l && r <= y) return st[i];
int mid = (l + r) >> 1;
return min(get(i << 1, l, mid, x, y), get(i << 1 | 1, mid + 1, r, x, y));
}
} F[2], G[2];
int Find(int v) { return v == p[v] ? v : p[v] = Find(p[v]); }
long long get(int l, int r)
{
if(l == r) return a[l][1];
long long ans = s[r] - s[l - 1], ex = 0, len = r - l + 1;
if(len % 2 == 1 && len > 2)
{
ex = F[(r - 1) % 2].get(1, 1, n, l, r - 1);
ex = min(ex, (long long)G[r % 2].get(1, 1, n, l + 1, r - 1));
ex = min({ex, 1LL * a[l][1] - a[l][2], 1LL * a[r][1] - a[r][2]});
}
return ans + ex;
}
void Us(int u, int v)
{
u = Find(u); v = Find(v);
if(u == v) return;
res -= get(L[u], R[u]) + get(L[v], R[v]);
L[u] = min(L[u], L[v]); R[u] = max(R[u], R[v]);
res += get(L[u], R[u]); p[v] = u;
}
vector<long long> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E)
{
n = W.size(); q = E.size();
f(i, 1, n) a[i][0] = W[i - 1], a[i][1] = A[i - 1], a[i][2] = B[i - 1];
f(i, 1, q) t[i].fi = E[i - 1], t[i].se = i;
vector <long long> cc(q); //cerr << q << "\n";
vector <arr(3)> e;
f(i, 1, 4 * n) F[0].st[i] = F[1].st[i] = G[0].st[i] = G[1].st[i] = inf;
sort(a + 1, a + n + 1);
sort(t + 1, t + q + 1);
f(i, 1, n) p[i] = i, L[i] = R[i] = i;
res = 0;
f(i, 1, n)
{
res += a[i][1];
s[i] = s[i - 1] + a[i][2];
if(i % 2 == 0) F[0].up(1, 1, n, i, a[i][1] - a[i][2]);
else F[1].up(1, 1, n, i, a[i][1] - a[i][2]);
}
f(i, 1, n - 1) e.pb({a[i + 1][0] - a[i][0], i, i + 1});
f(i, 2, n - 1) ee.eb(a[i + 1][0] - a[i - 1][0], i);
sort(e.begin(), e.end());
sort(ee.begin(), ee.end());
int j = 0, j2 = 0;
f(i, 1, q)
{
auto [d, id] = t[i];
while(j2 < (int)ee.size() && ee[j2].fi <= d)
{
int u = ee[j2].se;
G[u % 2].up(1, 1, n, u, a[u][1] - a[u][2]);
j2++;
}
while(j < n - 1 && e[j][0] <= d) Us(e[j][1], e[j][2]), j++;
cc[id - 1] = res;
//cerr << res << "\n";
}
return cc;
}
//signed main()
//{
// Keiiiii
// if(fopen("TASK.INP", "r"))
// {
// freopen("TASK.INP", "r", stdin);
// freopen("TASK.OUT", "w", stdout);
// }
// int n, q; cin >> n;
// vector <int> A(n), B(n), W(n);
// f(i, 0, n - 1) cin >> W[i] >> A[i] >> B[i];
// cin >> q;
// vector <int> E(q);
// f(i, 0, q - 1) cin >> E[i];
// vector <long long> ans = calculate_costs(W, A, B, E);
// for(auto x : ans) cout << x << "\n";
//}
