#include "nile.h"
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#include<malloc.h>
#include<cassert>
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
using pii = pair<ll,ll>;
using vi = vector<ll>;
using vpi = vector<pair<ll,ll>>;
ll N, Q, S, s;
vi output, F, D, C, odd, even, psum;
vpi w, e, moves;
struct ptree {
ll l, r, v, sz;
ptree *lc, *rc;
void construct(){
sz = r - l + 1;
v = 0;
if (l == r) return;
lc = (ptree*)(malloc(sizeof(ptree)));
rc = (ptree*)(malloc(sizeof(ptree)));
lc -> l = l;
rc -> r = r;
lc -> r = floor((l + r) / 2.0);
rc -> l = lc -> r + 1;
lc -> construct();
rc -> construct();
}
void update(ll pos){
if (l == r){
v = 1;
return;
}
if (pos <= lc -> r){
lc -> update(pos);
}
else {
rc -> update(pos);
}
if (lc -> v == lc -> sz){
v = lc -> v + rc -> v;
}
else {
v = lc -> v;
}
}
ll query(ll pos){
if (l == r){
return pos;
}
if (pos <= lc -> r){
return lc -> query(pos);
}
else {
if (rc -> v < pos - rc -> l + 1){
return rc -> query(pos);
}
else {
return lc -> query(lc -> r);
}
}
}
};
struct ec{
bool operator() (pii a, pii b){
return a.first < b.first;
}
};
inline ll conv(ll i){
return (ll)floor(i/2.0L);
}
struct stree {
ll l, r, v;
stree *lc, *rc;
void construct(){
this -> v = 1e9;
if (l == r) return;
this -> lc = (stree*)(malloc(sizeof(stree)));
this -> rc = (stree*)(malloc(sizeof(stree)));
lc -> l = l;
rc -> r = r;
lc -> r = (ll)floor((l+r)/2.0L);
rc -> l = lc -> r + 1;
lc -> construct();
rc -> construct();
}
void update(ll pos, ll val){
if (l == r){
v = val;
return;
}
if (pos <= lc -> r){
lc -> update(pos, val);
}
else {
rc -> update(pos, val);
}
v = min(lc -> v, rc -> v);
}
ll query(ll left, ll right){
if (right < left){
return 1e18;
}
if (left == l && right == r){
return v;
}
ll out = 1e18;
if (left <= lc -> r){
out = min(out,lc -> query(left, min(right, lc -> r)));
}
if (right >= rc -> l){
out = min(out,rc -> query(max(rc -> l, left), right));
}
return out;
}
};
stree oddr, evenr, oddf, evenf;
ptree root;
bool mc(pii a, pii b){
return w[a.second].first - w[a.first].first > w[b.second].first - w[b.first].first;
}
inline ll fc(ll i, ll choice){
return (i-choice)/2.0;
}
ll check_range(ll l, ll r){
ll out = psum[r+1] - psum[l];
if (r%2 != l%2) return out;
ll sub = 1e18;
if (l%2 == 0){
sub = min(evenf.query(fc(l,0), fc(r,0)), oddr.query(fc(l+1,1), fc(r-1,1)));
}
else {
sub = min(evenr.query(fc(l+1,0), fc(r-1,0)), oddf.query(fc(l,1), fc(r,1)));
}
return out - sub;
}
void makemove(){
pii cur = moves.back();
moves.pop_back();
if (cur.second - cur.first == 1){
s -= C[D[cur.first]];
s -= C[cur.second];
F[D[cur.first]] = F[cur.second];
D[F[cur.second]] = D[cur.first];
root.update(cur.second);
C[D[cur.first]] = check_range(D[cur.first], F[cur.second]);
s += C[D[cur.first]];
}
else {
ll p = cur.first + 1;
if (p%2 == 0){
evenr.update(fc(p, 0), w[p].second);
}
else {
oddr.update(fc(p, 1), w[p].second);
}
ll pos = root.query(p);
s -= C[pos];
C[pos] = check_range(pos, F[pos]);
s += C[pos];
}
//cerr << S - s << '\n';
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
Q = (ll)E.size();
N = (ll)W.size();
S = s = 0;
for (int i = 0; i < N; i++){
w.push_back({W[i], A[i] - B[i]});
S += A[i];
}
for (int i = 0; i < Q; i++){
e.push_back({E[i], i});
output.push_back(0);
}
sort(w.begin(), w.end(), ec());
sort(e.begin(), e.end(), ec());
psum.push_back(0);
oddr.v = 0;
oddr.l = 0;
oddr.r = conv(N-2);
evenr.v = 0;
evenr.l = 0;
evenr.r = conv(N-1);
oddf.v = 0;
oddf.l = 0;
oddf.r = conv(N-2);
evenf.v = 0;
evenf.l = 0;
evenf.r = conv(N-1);
root.l = 0;
root.r = N-1;
root.construct();
oddr.construct();
oddf.construct();
evenf.construct();
evenr.construct();
for (int i = 0; i < N; i++){
if (i%2 == 1){
oddf.update(fc(i, 1), w[i].second);
}
else {
evenf.update(fc(i,0), w[i].second);
}
psum.push_back(psum.back() + w[i].second);
F.push_back(i);
D.push_back(i);
C.push_back(0);
}
for (int i = 0; i < N-2; i++){
moves.push_back({i, i+2});
}
for (int i = 0; i < N-1; i++){
moves.push_back({i, i+1});
}
sort(moves.begin(), moves.end(), mc);
for (int i = 0; i < Q; i++){
while (moves.size() > 0){
if (w[moves.back().second].first - w[moves.back().first].first > e[i].first){
break;
}
makemove();
}
output[e[i].second] = S - s;
}
return output;
}
