#include "nile.h"
#include <vector>
#include <algorithm>
using ll = long long;
static const ll NEG_INF = -(1LL<<60);
// 2x2 max-plus matrix
struct Mat {
ll a[2][2];
};
// Max-plus multiplication: C = B * A
static Mat mmul(const Mat &B, const Mat &A) {
Mat C;
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
ll v = NEG_INF;
for(int k = 0; k < 2; k++) {
ll x = B.a[i][k] + A.a[k][j];
if(x > v) v = x;
}
C.a[i][j] = v;
}
}
return C;
}
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int N = (int)W.size();
int Q = (int)E.size();
// base sum if all alone
ll sumA = 0;
for(int i = 0; i < N; i++) sumA += A[i];
// handle trivial N=1
if(N == 1) {
std::vector<ll> R(Q, sumA);
return R;
}
// build items sorted by weight
struct Item { int w; ll d; };
std::vector<Item> it(N);
for(int i = 0; i < N; i++) {
it[i].w = W[i];
it[i].d = (ll)A[i] - (ll)B[i];
}
std::sort(it.begin(), it.end(), [](auto &L, auto &R){ return L.w < R.w; });
// compute gaps (gap, index)
// index k means between it[k-1] and it[k]
std::vector<std::pair<int,int>> gaps;
gaps.reserve(N-1);
for(int k = 1; k < N; k++) {
gaps.emplace_back(it[k].w - it[k-1].w, k);
}
std::sort(gaps.begin(), gaps.end());
// sort queries (D, original idx)
std::vector<std::pair<int,int>> qs(Q);
for(int j = 0; j < Q; j++) qs[j] = {E[j], j};
std::sort(qs.begin(), qs.end());
// build seg-tree size = next pow2 >= N
int SZ = 1;
while(SZ < N) SZ <<= 1;
std::vector<Mat> seg(2*SZ);
// identity matrix in max-plus
Mat I;
I.a[0][0] = 0; I.a[0][1] = NEG_INF;
I.a[1][0] = NEG_INF;I.a[1][1] = 0;
// off-edge matrix
Mat Off;
Off.a[0][0] = NEG_INF; Off.a[0][1] = 0;
Off.a[1][0] = NEG_INF; Off.a[1][1] = 0;
// init leaves
for(int i = 0; i < SZ; i++) {
if(i >= 1 && i < N) seg[SZ + i] = Off;
else seg[SZ + i] = I;
}
// build internals
for(int i = SZ-1; i >= 1; i--) {
seg[i] = mmul(seg[2*i+1], seg[2*i]);
}
std::vector<ll> R(Q);
int ptr = 0;
// process queries
for(auto &qq : qs) {
int D = qq.first;
int qi = qq.second;
// activate gaps with gap <= D
while(ptr < (int)gaps.size() && gaps[ptr].first <= D) {
int k = gaps[ptr].second;
// on-edge matrix at k
Mat On = Off;
ll sumd = it[k].d + it[k-1].d;
On.a[1][0] = sumd;
// update leaf k
int pos = SZ + k;
seg[pos] = On;
pos >>= 1;
while(pos) {
seg[pos] = mmul(seg[2*pos+1], seg[2*pos]);
pos >>= 1;
}
ptr++;
}
// seg[1] holds full product; matched = max(dp[N-1], dp[N]) = max(a[1][0], a[1][1])
Mat &M = seg[1];
ll matched = M.a[1][0] > M.a[1][1] ? M.a[1][0] : M.a[1][1];
R[qi] = sumA - matched;
}
return R;
}
