#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll, ll>> x;
//parent
vector<ll> par;
//ns = min(3 consec, and i+1-i-1)
vector<ll> ns;
//odd idx min, even idx min
vector<pair<ll, ll>> parity;
//l, r
vector<pair<ll, ll>> seg;
long long cur = 0;
int fpar(int k){
if(par[k] == k) return k;
par[k] = fpar(par[k]);
return par[k];
}
long long fmin(int k){
k = fpar(k);
if(seg[k].first%2 == 1 && (seg[k].second - seg[k].first + 1)%2 == 1){
return min(ns[k], parity[k].first);
}else if((seg[k].second - seg[k].first + 1)%2 == 1){
return min(ns[k], parity[k].second);
}
return 0;
}
void merge(int k, int v){
k = fpar(k);
v = fpar(v);
//k -> v
cur -= fmin(k);
cur -= fmin(v);
par[k] = v;
ns[v] = min(ns[v], ns[k]);
for(int y = max(seg[k].second-1, seg[k].first); y <= min(seg[v].first+1, seg[v].second); y++){
if(y+2 <= min(seg[v].first+1, seg[v].second)){
ns[v] = min(ns[v], x[y].second + x[y+1].second + x[y+2].second);
}
}
parity[v].first = min(parity[k].first, parity[v].first);
parity[v].second = min(parity[v].second, parity[k].second);
seg[v].first = seg[k].first;
//what to edit?
// cout << seg[v].first << " " << seg[v].second << endl;
// cout << ns[v] << " " << fmin(v) << "\n";
cur += fmin(v);
}
void upd(int y, ll k){
y = fpar(y);
cur -= fmin(y);
ns[y] = min(ns[y], k);
cur += fmin(y);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int Q = E.size();
vector<ll> R(Q);
x.resize(A.size());
ll j = 0;
for(int y = 0; y < A.size(); y++){
cur += A[y];
x[y].first = W[y];
j += A[y];
x[y].second = A[y] - B[y];
}
sort(x.begin(), x.end());
map<int, vector<int>> d;
for(int y = 0; y < x.size(); y++){
if(y+1 < x.size()){
d[x[y+1].first - x[y].first].push_back((y+1));
if(y-1 >= 0){
d[x[y+1].first - x[y-1].first].push_back(-(y+1));
}
}
}
vector<pair<int, ll>> ans = {{0, j}};
par.resize(x.size());
ns.resize(x.size());
parity.resize(x.size());
seg.resize(x.size());
for(int y = 0; y < x.size(); y++){
ns[y] = 1e18;
if(y%2 == 0){
parity[y].first = 1e18;
parity[y].second = x[y].second;
}else{
parity[y].first = x[y].second;
parity[y].second = 1e18;
}
seg[y] = {y, y};
par[y] = y;
}
for(auto y : d){
// cout << y.first << "AJDJAJDJADJ" << endl;
for(auto i : y.second){
if(i < 0){
i = abs(i);
i--;
upd(i, x[i].second);
}else{
i--;
merge(i, i+1);
}
}
// cout << cur << " BADIBADI\n";
ans.push_back({y.first, cur});
}
for(int y = 0; y < Q; y++){
long long m = 1e18;
auto it = lower_bound(ans.begin(), ans.end(), make_pair(E[y], m));
it--;
R[y] = it->second;
}
return R;
}
