#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pii = array<int,3>;
static const int MAXN = 100000, MAXT = 270000;
struct Mat {
lint A[3][3];
Mat() {
const lint INF = LLONG_MAX/3;
for(int i=0;i<3;i++) for(int j=0;j<3;j++)
A[i][j] = (i==j ? 0 : INF);
}
// min-plus matrix multiplication
Mat operator+(const Mat &m) const {
Mat r;
const lint INF = LLONG_MAX/3;
for(int i=0;i<3;i++) for(int j=0;j<3;j++)
r.A[i][j] = INF;
for(int i=0;i<3;i++) for(int k=0;k<3;k++)
for(int j=0;j<3;j++)
r.A[i][k] = min(r.A[i][k], A[i][j] + m.A[j][k]);
return r;
}
} M[MAXN];
struct SegTree {
int n, lim;
vector<Mat> st;
void init(int _n) {
n = _n;
lim = 1; while(lim < n) lim <<= 1;
st.assign(2*lim, Mat());
for(int i=0;i<n;i++) st[lim+i] = M[i];
for(int i=lim-1;i>0;i--) st[i] = st[2*i] + st[2*i+1];
}
void update(int p, const Mat &v) {
p += lim;
st[p] = v;
for(p>>=1; p; p>>=1)
st[p] = st[2*p] + st[2*p+1];
}
// root matrix = st[1]
};
vector<long long> calculate_costs(
vector<int> W, vector<int> A,
vector<int> B, vector<int> E
) {
int n = W.size();
vector<array<int,3>> a(n);
for(int i=0;i<n;i++)
a[i] = {W[i], A[i], B[i]};
sort(a.begin(), a.end()); // sort by weight
// Prepare events: (gap, left_index, right_index)
vector<array<int,3>> events;
for(int i=1;i<n;i++){
events.push_back({a[i][0]-a[i-1][0], i-1, i});
if(i>1)
events.push_back({a[i][0]-a[i-2][0], i-2, i});
}
sort(events.begin(), events.end(),
[](auto &x, auto &y){ return x[0]<y[0]; });
// Initialize leaf matrices
for(int i=0;i<n;i++){
// reset to INF-diagonal then set M[i].A[0][0]=A[i]
Mat m; const lint INF = LLONG_MAX/3;
for(int u=0;u<3;u++) for(int v=0;v<3;v++)
m.A[u][v] = INF;
m.A[0][0] = a[i][1];
m.A[1][0] = 0;
m.A[2][1] = 0;
M[i] = m;
}
SegTree seg; seg.init(n);
// Sweep D from 0 upward, recording (D, cost)
vector<pair<int, lint>> record;
record.emplace_back(0, seg.st[1].A[0][0]);
for(auto &ev : events){
int gap = ev[0], L = ev[1], R = ev[2];
Mat m = M[L];
// if R=L+1: pairing L and R
if(R == L+1){
m.A[0][1] = a[L][2] + a[R][2];
} else {
// triple grouping L, L+1, R
m.A[0][2] = a[L][2] + a[R][2] + a[L+1][1];
}
seg.update(L, m);
M[L] = m;
record.emplace_back(gap, seg.st[1].A[0][0]);
}
// Answer queries by binary searching record
vector<long long> ans(E.size());
vector<pair<int,int>> qs(E.size());
for(int i=0;i<(int)E.size();i++) qs[i] = {E[i], i};
sort(qs.begin(), qs.end());
int idx = 0;
for(auto &q : qs){
while(idx+1 < (int)record.size() && record[idx+1].first <= q.first)
idx++;
ans[q.second] = record[idx].second;
}
return ans;
}
