#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e16;
struct Matrix {
long long mat[3][3];
Matrix() {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
mat[i][j] = -INF;
}
};
struct Artifact {
int w, a, b;
long long p;
};
struct Edge {
int diff, type, idx;
bool operator<(const Edge& other) const {
return diff < other.diff;
}
};
int NN;
Matrix tree[400005];
bool act2[100005], act3[100005];
long long profits[100005];
Matrix merge(const Matrix& a, const Matrix& b) {
Matrix res;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
for (int l = 0; l + k <= 2; l++) {
res.mat[i][j] = max(res.mat[i][j], a.mat[i][k] + b.mat[l][j]);
}
}
}
}
return res;
}
void update_leaf(int v, int i) {
tree[v] = Matrix();
tree[v].mat[0][0] = 0;
if (act2[i]) tree[v].mat[1][1] = profits[i] + profits[i - 1];
if (act3[i]) tree[v].mat[2][2] = profits[i] + profits[i - 2];
}
void build(int v, int tl, int tr) {
if (tl == tr) {
update_leaf(v, tl);
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}
}
void update(int v, int tl, int tr, int pos) {
if (tl == tr) {
update_leaf(v, tl);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) update(2 * v, tl, tm, pos);
else update(2 * v + 1, tm + 1, tr, pos);
tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}
}
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();
NN = n;
vector<Artifact> arts(n);
long long total_a = 0;
for (int i = 0; i < n; i++) {
arts[i] = {W[i], A[i], B[i], (long long)A[i] - B[i]};
total_a += A[i];
}
sort(arts.begin(), arts.end(), [](const Artifact& x, const Artifact& y) {
return x.w < y.w;
});
for (int i = 0; i < n; i++) profits[i] = arts[i].p;
vector<Edge> edges;
for (int i = 1; i < n; i++) edges.push_back({arts[i].w - arts[i - 1].w, 2, i});
for (int i = 2; i < n; i++) edges.push_back({arts[i].w - arts[i - 2].w, 3, i});
sort(edges.begin(), edges.end());
vector<pair<int, int>> queries(q);
for (int i = 0; i < q; i++) queries[i] = {E[i], i};
sort(queries.begin(), queries.end());
build(1, 0, n - 1);
vector<long long> results(q);
int edge_ptr = 0;
for (int i = 0; i < q; i++) {
while (edge_ptr < edges.size() && edges[edge_ptr].diff <= queries[i].first) {
if (edges[edge_ptr].type == 2) act2[edges[edge_ptr].idx] = true;
else act3[edges[edge_ptr].idx] = true;
update(1, 0, n - 1, edges[edge_ptr].idx);
edge_ptr++;
}
long long max_profit = -INF;
for (int r = 0; r < 3; r++) max_profit = max(max_profit, tree[1].mat[0][r]);
results[queries[i].second] = total_a - max_profit;
}
return results;
}
