#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 1e5 + 5, INF = 1e18;
int n;
arr<pii, N> a;
arr<int, N> sm;
vec<vec<int>> ev;
struct Dsj {
arr<int, N> prnt, lf, rg;
arr<arr<int, 2>, N> mn, ex;
void intl() {
for (int u = 1; u <= n; u++) {
prnt[u] = lf[u] = rg[u] = u;
mn[u][u % 2] = a[u].sec, mn[u][!(u % 2)] = INF;
ex[u][0] = ex[u][1] = INF;
}
}
int pr(int u) {
return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
}
void mrg(int u, int v) {
u = pr(u), v = pr(v);
assert(u != v);
assert(rg[u] == lf[v] - 1);
prnt[v] = u, rg[u] = rg[v];
for (int i : {0, 1}) {
mn[u][i] = min(mn[u][i], mn[v][i]);
ex[u][i] = min(ex[u][i], ex[v][i]);
}
}
void upd(int u) {
ex[pr(u)][u % 2] = min(ex[pr(u)][u % 2], a[u].sec);
}
int evl(int u) {
u = pr(u);
int ans = sm[rg[u]] - sm[lf[u] - 1];
int sz = rg[u] - lf[u] + 1;
if (sz % 2 == 1) ans -= min({mn[u][lf[u] % 2], ex[u][!(lf[u] % 2)]});
return ans;
}
} dsj;
void prp_cmp() {
for (int i = 1; i <= n; i++)
sm[i] = sm[i - 1] + a[i].sec;
for (int i = 1; i <= n - 1; i++)
ev.push_back({a[i + 1].fir - a[i].fir, i, i + 1});
for (int i = 2; i <= n - 1; i++)
ev.push_back({a[i + 1].fir - a[i - 1].fir, i});
sort(ev.begin(), ev.end());
// for (vec<int> x : ev) {
// for (int y : x) cout << y << " ";
// cout << '\n';
// }
dsj.intl();
}
vec<pii> crt;
void crt_cmp() {
crt.push_back({0, 0});
int ans = 0;
for (vec<int> x : ev) {
if (x.size() == 3) {
int d = x[0], u = x[1], v = x[2];
ans -= dsj.evl(u), ans -= dsj.evl(v);
dsj.mrg(u, v);
ans += dsj.evl(u);
crt.push_back({d, ans});
} else {
int d = x[0], u = x[1];
ans -= dsj.evl(u);
dsj.upd(u);
ans += dsj.evl(u);
crt.push_back({d, ans});
}
}
}
vec<int> calculate_costs(vec<sig> _ps, vec<sig> _fl, vec<sig> _pr, vec<sig> _qr) {
n = _ps.size();
int whl = 0;
for (int i = 1; i <= n; i++) {
a[i] = {_ps[i - 1], _fl[i - 1] - _pr[i - 1]};
whl += _fl[i - 1];
}
sort(a.begin() + 1, a.begin() + n + 1);
prp_cmp();
crt_cmp();
vec<int> ans;
for (int d : _qr) {
int lw = 0, hg = crt.size() - 1;
while (lw < hg) {
int md = (lw + hg + 1) / 2;
if (d >= crt[md].fir) lw = md;
else hg = md - 1;
}
ans.push_back(whl - crt[lw].sec);
}
return ans;
}
