#include <vector>
#include <algorithm>
#include "nile.h"
using namespace std;
const long long INF = 1e18;
struct Matrix {
long long m[3][3];
Matrix() {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
m[i][j] = INF;
}
};
struct Artifact {
int w, a, b;
};
Matrix merge(const Matrix& A, const Matrix& B) {
Matrix C;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
// Combine ranges such that the total number of items
// used across the boundary maintains the correct offset.
C.m[i][j] = min(C.m[i][j], A.m[i][k] + B.m[k][j]);
}
}
}
return C;
}
int SZ;
Matrix tree[400005];
bool can_pair2[100005], can_pair3[100005];
Artifact sorted_arts[100005];
void update_node(int v, int idx) {
tree[v] = Matrix();
// Case 1: Send artifact alone (Cost A)
tree[v].m[0][1] = sorted_arts[idx].a;
tree[v].m[1][2] = sorted_arts[idx].a;
tree[v].m[2][0] = sorted_arts[idx].a;
// Case 2: Send in a pair (Cost B)
// Offset logic handles the parity of pairs
if (can_pair2[idx]) {
tree[v].m[0][2] = min(tree[v].m[0][2], (long long)sorted_arts[idx].b + sorted_arts[idx - 1].b);
tree[v].m[1][0] = min(tree[v].m[1][0], (long long)sorted_arts[idx].b + sorted_arts[idx - 1].b);
tree[v].m[2][1] = min(tree[v].m[2][1], (long long)sorted_arts[idx].b + sorted_arts[idx - 1].b);
}
// Case 3: Skip one (triple range)
if (can_pair3[idx]) {
tree[v].m[0][0] = min(tree[v].m[0][0], (long long)sorted_arts[idx].b + sorted_arts[idx - 2].b + sorted_arts[idx - 1].a);
tree[v].m[1][1] = min(tree[v].m[1][1], (long long)sorted_arts[idx].b + sorted_arts[idx - 2].b + sorted_arts[idx - 1].a);
tree[v].m[2][2] = min(tree[v].m[2][2], (long long)sorted_arts[idx].b + sorted_arts[idx - 2].b + sorted_arts[idx - 1].a);
}
}
void build(int v, int tl, int tr) {
if (tl == tr) {
update_node(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_node(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();
vector<pair<int, int>> temp(n);
for (int i = 0; i < n; i++) temp[i] = {W[i], i};
sort(temp.begin(), temp.end());
for (int i = 0; i < n; i++) {
sorted_arts[i] = {W[temp[i].second], A[temp[i].second], B[temp[i].second]};
}
vector<pair<int, int>> edges;
for (int i = 1; i < n; i++) edges.push_back({sorted_arts[i].w - sorted_arts[i - 1].w, i});
for (int i = 2; i < n; i++) edges.push_back({sorted_arts[i].w - sorted_arts[i - 2].w, i + n});
sort(edges.begin(), edges.end());
int q = E.size();
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 ptr = 0;
for (int i = 0; i < q; i++) {
while (ptr < edges.size() && edges[ptr].first <= queries[i].first) {
int val = edges[ptr].second;
if (val < n) {
can_pair2[val] = true;
update(1, 0, n - 1, val);
} else {
can_pair3[val - n] = true;
update(1, 0, n - 1, val - n);
}
ptr++;
}
results[queries[i].second] = tree[1].m[0][n % 3];
}
return results;
}
