#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
struct object {
int w, a, b;
};
struct query {
int e, i;
};
struct update {
int d, i;
};
const int MAX_N = 1e5;
object objects[MAX_N];
query queries[MAX_N];
update updates[MAX_N];
update updates2[MAX_N];
int parent[MAX_N], sz[MAX_N], lft[MAX_N], rght[MAX_N];
long long sumB[MAX_N];
int minAB[MAX_N], minAB0[MAX_N], minAB1[MAX_N];
long long cost;
int ab(int i) {
return objects[i].a - objects[i].b;
}
int findParent(int x) {
if (parent[x] != x)
parent[x] = findParent(parent[x]);
return parent[x];
}
void unionn(int x, int y) {
x = findParent(x);
y = findParent(y);
cost -= sumB[x];
if (sz[x] % 2 == 1)
cost -= min(minAB0[x], minAB[x]);
cost -= sumB[y];
if (sz[y] % 2 == 1)
cost -= min(minAB0[y], minAB[y]);
sumB[x] += sumB[y];
minAB[x] = min(minAB[x], minAB[y]);
if (sz[x] % 2 == 1) {
minAB0[x] = min(minAB0[x], minAB1[y]);
minAB1[x] = min(minAB1[x], minAB0[y]);
} else {
minAB0[x] = min(minAB0[x], minAB0[y]);
minAB1[x] = min(minAB1[x], minAB1[y]);
}
sz[x] += sz[y];
parent[y] = x;
rght[x] = max(rght[x], rght[y]);
lft[x] = min(lft[x], lft[y]);
cost += sumB[x];
if (sz[x] % 2 == 1)
cost += min(minAB0[x], minAB[x]);
}
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = w.size();
int q = e.size();
vector<long long> ans(q);
for (int i = 0; i < n; i++)
objects[i] = {w[i], a[i], b[i]};
for (int i = 0; i < q; i++)
queries[i] = {e[i], i};
sort(objects, objects + n, [](object x, object y) {
return x.w < y.w;
});
sort(queries, queries + q, [](query x, query y) {
return x.e < y.e;
});
for (int i = 0; i < n - 1; i++)
updates[i] = {objects[i + 1].w - objects[i].w, i};
sort(updates, updates + n - 1, [](update x, update y) {
return x.d < y.d;
});
for (int i = 1; i < n - 1; i++)
updates2[i] = {objects[i + 1].w - objects[i - 1].w, i};
sort(updates2 + 1, updates2 + n - 1, [](update x, update y) {
return x.d < y.d;
});
cost = 0;
for (int i = 0; i < n; i++)
cost += objects[i].a;
for (int i = 0; i < n; i++) {
parent[i] = i;
sumB[i] = objects[i].b;
minAB[i] = 1e9;
minAB0[i] = objects[i].a - objects[i].b;
minAB1[i] = 1e9;
lft[i] = rght[i] = i;
sz[i] = 1;
}
int j = 0, l = 1;
for (int i = 0; i < q; i++) {
while (j < n - 1 && updates[j].d <= queries[i].e) {
unionn(updates[j].i, updates[j].i + 1);
j++;
}
while (l < n - 1 && updates2[l].d <= queries[i].e) {
int p = findParent(updates2[l].i);
if (sz[p] % 2 == 1)
cost -= min(minAB0[p], minAB[p]);
minAB[p] = min(minAB[p], ab(updates2[l].i));
if (sz[p] % 2 == 1)
cost += min(minAB0[p], minAB[p]);
l++;
}
// printf("QUERY %d\n", queries[i].e);
ans[queries[i].i] = cost;
}
return ans;
}
