#include "nile.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5+5, INF = 1e9+5;
int N, Q, C[MAXN], P[MAXN], Z[MAXN], even[MAXN], odd[MAXN], can[MAXN];
ll ans;
pii SW[MAXN], SE[MAXN], S[2*MAXN];
int find(int x) {
if (P[x] == x) {
return x;
}
return P[x] = find(P[x]);
}
int score(int p) {
if (Z[p]&1) {
return min(can[p],odd[p]);
}
return 0;
}
void join(int x,int y) {
x = find(x);
y = find(y);
ans -= score(x);
ans -= score(y);
can[x] = min(can[x],can[y]);
if (Z[x]&1) {
odd[x] = min(odd[x],even[y]);
even[x] = min(even[x],odd[y]);
}
else {
odd[x] = min(odd[x],odd[y]);
even[x] = min(even[x],even[y]);
}
P[y] = x;
Z[x] += Z[y];
ans += score(x);
}
void add(int x) {
int px = find(x);
ans -= score(px);
can[px] = min(can[px],C[x]);
ans += score(px);
}
vector<ll> calculate_costs(vector<int> W,vector<int> A,vector<int> B,vector<int> E) {
N = W.size();
Q = E.size();
vector <ll> res(Q);
for (int i=0;i<N;i++) {
SW[i] = {W[i],i};
ans += A[i];
}
sort(SW,SW+N);
for (int i=0;i<N;i++) {
P[i] = i;
Z[i] = 1;
odd[i] = C[i] = A[SW[i].se]-B[SW[i].se];
even[i] = can[i] = INF;
}
for (int i=1;i<N;i++) {
S[i] = {SW[i].fi-SW[i-1].fi,i};
}
for (int i=1;i<N-1;i++) {
S[i+N-1] = {SW[i+1].fi-SW[i-1].fi,-i};
}
sort(S+1,S+2*N-2);
S[2*N-2].fi = INF;
for (int i=0;i<Q;i++) {
SE[i] = {E[i],i};
}
sort(SE,SE+Q);
for (int i=0,j=1;i<Q;i++) {
while (S[j].fi <= SE[i].fi) {
if (S[j].se > 0) {
join(S[j].se-1,S[j].se);
}
else {
add(-S[j].se);
}
j++;
}
res[SE[i].se] = ans;
}
return res;
}
