#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
ll w1[N] , a1[N] , b1[N];
ll w[N] , a[N] , b[N] , ord[N] , d[N] , c[N] , n , q;
vector<long long> solve(){
vector<ll> vec;
for(int _ = 1; _ <= q; _++){
ll sum = 0;
for(int i = 1; i <= n; i++){
a1[i] = a[i];
b1[i] = b[i];
w1[i] = w[i];
}
for(int i = 1; i <= n; i++){
sum += b[i];
ord[i] = i;
}
sort(ord+1,ord+1+n,[&](int i , int j){
return w[i] < w[j];
});
for(int i = 1; i <= n; i++){
a[i] = a1[ord[i]];
b[i] = b1[ord[i]];
w[i] = w1[ord[i]];
c[i] = a[i]-b[i];
}
for(int l = 1; l <= n; l++){
ll k = l , mn = INF;
while(k+1 <= n && abs(w[k]-w[k+1]) <= d[_]) k++;
for(int j = l; j <= k; j++){
if(j % 2 != l % 2){
if(j+1 <= n && j-1 >= 1 && abs(w[j-1]-w[j+1]) <= d[_]){
mn = min(mn , c[j]);
}
} else {
mn = min(mn , c[j]);
}
}
l = k;
sum += mn;
}
vec.push_back(sum);
}
return vec;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
n = W.size();
for(int i = 1; i <= n; i++){
w[i] = W[i-1];
a[i] = A[i-1];
b[i] = B[i-1];
}
q = E.size();
for(int i = 1; i <= q; i++){
d[i] = E[i-1];
}
return solve();
}
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> W(N), A(N), B(N);
// for (int i = 0; i < N; i++)
// assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> E(Q);
// for (int j = 0; j < Q; j++)
// assert(1 == scanf("%d", &E[j]));
// fclose(stdin);
//
// std::vector<long long> R = calculate_costs(W, A, B, E);
//
// int S = (int)R.size();
// for (int j = 0; j < S; j++)
// printf("%lld\n", R[j]);
// fclose(stdout);
//
// return 0;
// }
