#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> calculate_costs( vector<int> W, vector<int> A, vector<int> B, vector<int> Q ){
int n = W.size();
int q = Q.size();
vector<int> inds(n);
iota(inds.begin(),inds.end(),0);
sort(inds.begin(),inds.end(),[&](int a,int b){
return W[a] < W[b];
});
vector<ll> weights(n), penalty(n);
for( int i = 0; i < n; i++ ){
weights[i] = W[inds[i]];
penalty[i] = A[inds[i]] - B[inds[i]];
}
vector<pair<ll,int>> events;
events.push_back( {LLONG_MAX,-1} );
for( int i = 0; i < n-1; i++ )
events.push_back( {weights[i+1]-weights[i],2*i} );
for( int i = 0; i < n-2; i++ )
events.push_back( {weights[i+2]-weights[i],2*i+1} );
sort(events.rbegin(),events.rend());
vector<ll> output(q);
inds.resize(q);
iota(inds.begin(),inds.end(),0);
sort(inds.begin(),inds.end(),[&](int a,int b){
return Q[a] < Q[b];
});
ll ans = 0;
for( auto e: A ) ans += e;
set<int> bounds;
for( int i = 0; i <= n; i++ ) bounds.insert(i);
vector<ll> segpenalty = penalty;
vector<ll> mineven(n,LLONG_MAX);
vector<ll> minodd(n,LLONG_MAX);
vector<ll> togeven(n,LLONG_MAX);
vector<ll> togodd(n,LLONG_MAX);
for( int i = 0; i < n; i++ ){
if( i%2 == 0 ) mineven[i] = penalty[i];
else minodd[i] = penalty[i];
}
for( int i = 0; i < q; i++ ){
ll query = Q[inds[i]];
while( events.back().first <= query ){
int ev = events.back().second; events.pop_back();
int x = ev/2;
if( ev%2 == 0 ){
auto it = bounds.upper_bound(x);
int L = *prev(it), M = *it, R = *next(it);
bounds.erase(M);
ans -= segpenalty[L];
ans -= segpenalty[M];
mineven[L] = min(mineven[L],mineven[M]);
minodd[L] = min(minodd[L],minodd[M]);
togeven[L] = min(togeven[L],togeven[M]);
togodd[L] = min(togodd[L],togodd[M]);
if( (R-L)%2 == 0 ){
segpenalty[L] = 0;
} else {
if( L%2 == 0 ) segpenalty[L] = min(mineven[L],togodd[L]);
else segpenalty[L] = min(minodd[L],togeven[L]);
}
ans += segpenalty[L];
} else {
auto it = bounds.upper_bound(x);
int L = *prev(it), R = *it;
ans -= segpenalty[L];
if( (x+1)%2 == 0 ) togeven[L] = min(togeven[L], penalty[x+1]);
else togodd[L] = min(togodd[L], penalty[x+1]);
if( (R-L)%2 == 0 ){
segpenalty[L] = 0;
} else {
if( L%2 == 0 ) segpenalty[L] = min(mineven[L],togodd[L]);
else segpenalty[L] = min(minodd[L],togeven[L]);
}
ans += segpenalty[L];
}
}
output[inds[i]] = ans;
}
return output;
}
