#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
ll a[3][3];
} t[(1 << 19)];
int n;
ll cd, dp[20];
vector<array<ll, 3>> v;
bool ok(int i, int j) {
if (i < 0 || j >= n)return false;
return (v[j][0] - v[i][0] <= cd);
}
ll pr(int i, int j) {
return v[i][1] + v[j][1];
}
ll clc(int l, int r) {
if (l == r)return v[l][2];
int sz = r-l+1;
dp[sz] = 0;
for (int j = sz-1, cur = r; j >= 0; j--, cur--) {
dp[j] = v[cur][2] + dp[j+1];
if (j+1 < sz && ok(cur, cur+1)) {
dp[j] = min(dp[j], pr(cur, cur+1) + dp[j+2]);
}
if (j+2 < sz && ok(cur, cur+2)) {
dp[j] = min(dp[j], dp[j+3] + pr(cur, cur+2) + v[cur+1][2]);
}
}
return dp[0];
}
void calc(int l, int r, int x) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i + j > r - l + 1) {
t[x].a[i][j] = 1e18;
continue;
}
t[x].a[i][j] = clc(l + i, r - j);
}
}
}
node merge(node &lef, node &rig, int m) {
node ret;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ret.a[i][j] = lef.a[i][0] + rig.a[0][j];
if (ok(m, m+1)) {
ret.a[i][j] = min(ret.a[i][j], lef.a[i][1] + rig.a[1][j] + pr(m, m+1));
}
if (ok(m, m+2)) {
ret.a[i][j] = min(ret.a[i][j], lef.a[i][1] + rig.a[2][j] + pr(m, m+2) + v[m+1][2]);
}
if (ok(m-1, m+1)) {
ret.a[i][j] = min(ret.a[i][j], lef.a[i][2] + rig.a[1][j] + pr(m-1, m+1) + v[m][2]);
}
}
}
return ret;
}
void build(int l, int r, int x) {
if (l == r) {
calc(l, r, x);
return;
}
int m = (l + r) >> 1;
build(l, m, x * 2 + 1);
build(m+1, r, x * 2 + 2);
if (min(m-l+1, r-m) < 4) {
calc(l, r, x);
return;
}
t[x] = merge(t[x*2+1], t[x*2+2], m);
}
void upd(int l, int r, int x, int i) {
if (l == r)return;
int m = (l + r) >> 1;
if (i <= m) {
upd(l, m, x * 2 + 1, i);
} else {
upd(m+1, r, x * 2 + 2, i);
}
if (min(m-l+1, r-m) < 4) {
calc(l, r, x);
return;
}
t[x] = merge(t[x*2+1], t[x*2+2], m);
}
void init() {
cd = 0;
build(0, n - 1, 0);
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int q = E.size();
vector<ll> ans(q);
n = W.size();
vector<pair<int, int>> qr(q);
for (int i = 0; i < q; i++) {
qr[i] = {E[i], i};
}
v.resize(n);
for (int i = 0; i < n; i++) {
v[i] = {W[i], B[i], A[i]};
}
sort(qr.begin(), qr.end());
sort(v.begin(), v.end());
init();
vector<pair<int, int>> a;
for (int i = 1; i < n; i++) {
a.push_back({v[i][0] - v[i-1][0], i});
if (i > 1)a.push_back({v[i][0] - v[i-2][0], i});
}
sort(a.begin(), a.end());
int cur = 0;
for (auto &[d, id] : qr) {
cd = d;
while (cur < a.size() && a[cur].first <= cd) {
upd(0, n-1, 0, a[cur++].second);
}
ans[id] = t[0].a[0][0];
}
return ans;
}
