#include "nile.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
using namespace std;
struct dta{
ll w, g;
bool operator<(const dta &a) const{
return w < a.w;
}
};
struct dta2{
ll fir, scc, m;
bool operator<(const dta2 &a) const{
if(fir == a.fir){
if(scc == a.scc) return m < a.m;
return scc < a.scc;
}return fir < a.fir;
}
};
vll pw(20, 1);
ll mn(vector<vll> &st1, vector<vll> &st2, ll l, ll r, ll m){
if((r-l+1) % 2 == 0)return 0;
ll lg = log2(r-l+1);
if(l % 2){
return min({st2[lg][l], st2[lg][r - pw[lg] + 1], m});
}else{
return min({st1[lg][l], st1[lg][r - pw[lg] + 1], m});
}
}
vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
ll n = W.size();
vector<dta> a(n);
for(ll i = 0; i < n; i++){
a[i] = {W[i], A[i]-B[i]};
}sort(a.begin(), a.end());
vector<pairll> gap(n-1);
for(ll i = 1; i < n; i++){
gap[i-1] = {a[i].w-a[i-1].w, i};
}sort(gap.begin(), gap.end());
vector<pairll> gap2(n-2);
for(ll i = 2; i < n; i++){
gap2[i-2] = {a[i].w-a[i-2].w, i};
}sort(gap2.begin(), gap2.end());
vector<vll> st1(20, vll(n, 1e18)), st2(20, vll(n, 1e18));
for(ll i = 1; i < 20; i++) pw[i] = pw[i-1]*2;
for(ll i = 0; i < n; i+=2) st1[0][i] = a[i].g;
for(ll i = 1; i < 20; i++){
for(ll j = 0; j + pw[i]-1 < n; j++){
st1[i][j] = min(st1[i-1][j], st1[i-1][j+pw[i-1]]);
}
}
for(ll i = 1; i < n; i+=2) st2[0][i] = a[i].g;
for(ll i = 1; i < 20; i++){
for(ll j = 0; j + pw[i]-1 < n; j++){
st2[i][j] = min(st2[i-1][j], st2[i-1][j+pw[i-1]]);
}
}
// for(ll i = 0; i < 3; i++){
// for(ll j = 0; j < n; j++){
// cout << st[i][j] << ' ';
// }cout << endl;
// }
multiset<dta2> s; ll inf = 1e18;
for(ll i = 0; i < n; i++) s.insert({i, i, inf});
vector<pairll> q(E.size());
for(ll i = 0; i < q.size(); i++) q[i] = {E[i], i};
sort(q.begin(), q.end());
ll tot = 0;
for(ll i = 0; i < n; i++)tot += A[i];
vll res(E.size());
ll k = 0, kk = 0;
for(pairll x : q){
while(k < n-1){
if(gap[k].fi > x.fi)break;
// cout << gap[k].fi << ' ' << gap[k].sc << endl;
auto it1 = s.lower_bound({gap[k].sc, 0, 0});
auto it2 = s.lower_bound({gap[k].sc, 0, 0}); it2--;
tot -= mn(st1, st2, (*it1).fir, (*it1).scc, (*it1).m);
tot -= mn(st1, st2, (*it2).fir, (*it2).scc, (*it2).m);
// cout << (*it1).fir << ' ' << (*it1).scc << ' ';
// cout << (*it2).fir << ' ' << (*it2).scc << endl;
// cout << tot << endl;
ll mm = min((*it1).m, (*it2).m);
tot += mn(st1, st2, (*it2).fir, (*it1).scc, mm);
// cout << tot << endl << endl;
s.insert({(*it2).fir, (*it1).scc, mm});
s.erase(it1); s.erase(it2);
k++;
}
// cout << tot << endl;
while(kk < n-2){
if(gap2[kk].fi > x.fi)break;
auto it = s.lower_bound({gap2[kk].sc, 0, 0}); it--;
tot -= mn(st1, st2, (*it).fir, (*it).scc, (*it).m);
ll mm = min((*it).m, a[gap2[kk].sc-1].g);
tot += mn(st1, st2, (*it).fir, (*it).scc, mm);
s.insert({(*it).fir, (*it).scc, mm});
s.erase(it);
kk++;
}
// cout << tot << endl << endl;
res[x.sc] = tot;
}
return res;
}
