#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define cerr if(0) cerr
#define all(x) x.begin(),x.end()
#define ll long long int
const int N = 1e5+100;
int _n;
ll T[N*2], T2[2*N];
void build(int n){
_n = n;
for(int j = 0; j <= 2*n+2; ++j) T[j] = T2[j] = 1e18;
}
void upd(int p, ll val){
++p;
if(p&1){
T[p += _n] = val;
for(p >>= 1; p; p >>= 1) T[p] = min(T[p<<1], T[p<<1|1]);
}else{
T2[p += _n] = val;
for(p >>= 1; p; p >>= 1) T2[p] = min(T2[p<<1], T2[p<<1|1]);
}
}
void upd2(int p, ll val){
++p;
if(!(p&1)){
T[p += _n] = val;
for(p >>= 1; p; p >>= 1) T[p] = min(T[p<<1], T[p<<1|1]);
}else{
T2[p += _n] = val;
for(p >>= 1; p; p >>= 1) T2[p] = min(T2[p<<1], T2[p<<1|1]);
}
}
ll get(int l, int r){
if(l > r) return 1e18;
ll res = 1e18;
++l, ++r;
if(l&1){
l += _n;
r += _n + 1;
for(; l < r; l >>= 1, r >>= 1){
if(l&1) res = min(res, T[l++]);
if(r&1) res = min(res, T[--r]);
}
}else{
l += _n;
r += _n + 1;
for(; l < r; l >>= 1, r >>= 1){
if(l&1) res = min(res, T2[l++]);
if(r&1) res = min(res, T2[--r]);
}
}
return res;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int q = (int) E.size();
int n = (int) W.size();
build(n);
vector<array<ll, 3>> C;
for(int i = 0; i < n; ++i) C.pb({W[i], A[i], B[i]});
sort(all(C));
vector<ll> pref(n);
ll sum = 0;
for(int i = 0; i < n; ++i) sum += C[i][1];
pref[0] = C[0][1] - C[0][2];
for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + C[i][1] - C[i][2];
for(int i = 0; i < n; ++i) upd(i, C[i][1] - C[i][2]);
// for(int i = 0; i < n; ++i) cerr << pref[i] << ' ';
// cerr << " wtf\n";
function<ll(int, int)> get2 = [&](int l, int r){
if(l == r) return 0ll;
if((r-l) % 2){
return pref[r] - (l <= 0 ? 0 : pref[l - 1]);
}
ll summ = pref[r] - (l <= 0 ? 0 : pref[l - 1]);
return summ - get(l, r);
};
vector<ll> res(q);
vector<pair<ll, int>> Q;
for(int i = 0; i < q; ++i) Q.pb({E[i], i});
sort(all(Q));
set<array<int, 2>> S;
for(int i = 0; i < n; ++i) S.insert({i, i});
vector<pair<ll, ll>> dif;
vector<pair<ll, ll>> adj;
for(int i = 1; i < n; ++i) dif.pb({C[i][0] - C[i - 1][0], i});
for(int i = 1; i + 1 < n; ++i) adj.pb({C[i + 1][0] - C[i - 1][0], i});
sort(all(dif));
sort(all(adj));
int ptr = 0;
int ptr2 = 0;
ll ans = 0;
for(auto [D, idx]: Q){
cerr << D << ":\n";
while(ptr2 + 2 < n && adj[ptr2].ff <= D){
int pt = adj[ptr2].ss;
auto it = S.lower_bound(array<int, 2>{pt + 1, -1});
--it;
ans -= get2((*it)[0], (*it)[1]);
upd2(pt, C[pt][1] - C[pt][2]);
ans += get2((*it)[0], (*it)[1]);
cerr << pt << ' ';
ptr2++;
}
cerr << '\n';
while(ptr + 1 < n && dif[ptr].ff <= D){
int pt = dif[ptr].ss;
// cerr << pt << ' ';
auto it = S.lower_bound(array<int, 2>{pt, -1});
ans -= get2((*it)[0], (*it)[1]);
ans -= get2((*prev(it))[0], (*prev(it))[1]);
int L = (*prev(it))[0];
int R = (*it)[1];
S.erase(prev(it));
it = S.lower_bound(array<int, 2>{pt, -1});
S.erase(it);
S.insert({L, R});
// cerr << L << ' ' << R << ' ' << get2(L, R) << " ff\n";
ans += get2(L, R);
++ptr;
}
cerr << '\n';
cerr << ans << '\n';
cerr << "S:\n";
res[idx] = sum - ans;
}
return res;
}
