#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define F first
#define S second
typedef long long ll;
const int N = 1e5 + 10;
int n, q, sz[N], mn[N][3], par[N];
ll res, sm[N], ans[N];
vector<int> w, a, b, e;
vector<ll> output;
int root(int v){
return (par[v] == -1 ? v : par[v] = root(par[v]));
}
void merge(int u, int v){
if ((u = root(u)) == (v = root(v)))
return ;
res -= ans[u], res -= ans[v];
par[u] = v;
sm[v] += sm[u];
if (sz[v] % 2){
mn[v][0] = min(mn[v][0], mn[u][1]);
mn[v][1] = min(mn[v][1], mn[u][0]);
}
else{
mn[v][0] = min(mn[v][0], mn[u][0]);
mn[v][1] = min(mn[v][1], mn[u][1]);
}
mn[v][2] = min(mn[v][2], mn[u][2]);
sz[v] += sz[u];
ans[v] = sm[v] + min(mn[v][1], mn[v][2]) * (sz[v] % 2);
res += ans[v];
}
void upd(int u){
int v = root(u);
mn[v][2] = min(mn[v][2], a[u] - b[u]);
res -= ans[v];
ans[v] = sm[v] + min(mn[v][1], mn[v][2]) * (sz[v] % 2);
res += ans[v];
}
vector<ll> calculate_costs(vector<int> ww, vector<int> aa, vector<int> bb, vector<int> ee) {
n = (int)ww.size(), q = (int)ee.size();
w = ww, a = aa, b = bb, e = ee;
output.resize(q, 0);
vector<pair<int, pair<int, int>>> vec;
for (int i = 0; i < n; i ++)
vec.push_back({w[i], {a[i], b[i]}});
sort(vec.begin(), vec.end());
for (int i = 0; i < n; i ++)
w[i] = vec[i].F, a[i] = vec[i].S.F, b[i] = vec[i].S.S;
vector<pair<int, int>> que;
for (int i = 0; i < q; i ++)
que.push_back({e[i], i});
sort(que.begin(), que.end());
vector<pair<int, int>> edges[2];
for (int i = 1; i < n; i ++){
edges[0].push_back({w[i] - w[i - 1], i});
if (i + 1 < n)
edges[1].push_back({w[i + 1] - w[i - 1], i});
}
for (int id : {0, 1}){
sort(edges[id].begin(), edges[id].end());
reverse(edges[id].begin(), edges[id].end());
}
for (int v = 0; v < n; v ++){
sz[v] = 1, sm[v] = b[v], par[v] = -1;
mn[v][0] = mn[v][2] = 1e9, mn[v][1] = a[v] - b[v];
ans[v] = a[v];
res += ans[v];
}
for (auto [d, id] : que){
while (!edges[0].empty() and (edges[0].back()).F <= d){
int i = (edges[0].back()).S;
merge(i, i - 1);
edges[0].pop_back();
}
while (!edges[1].empty() and (edges[1].back()).F <= d){
int i = (edges[1].back()).S;
upd(i);
edges[1].pop_back();
}
output[id] = res;
}
return output;
}
