#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];
int parent[MAX_N], sz[MAX_N];
long long sumB[MAX_N], minAB[MAX_N];
long long cost;
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 -= minAB[x];
cost -= sumB[y];
if (sz[y] % 2 == 1)
cost -= minAB[y];
sumB[x] += sumB[y];
minAB[x] = min(minAB[x], minAB[y]);
sz[x] += sz[y];
parent[y] = x;
cost += sumB[x];
if (sz[x] % 2 == 1)
cost += 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;
});
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] = objects[i].a - objects[i].b;
sz[i] = 1;
}
int j = 0;
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);
// printf("UNESC %d %d\n", updates[j].i, updates[j].i + 1);
j++;
}
// printf("QUERY %d\n", queries[i].e);
ans[queries[i].i] = cost;
}
return ans;
}
