#include "nile.h"
#include <vector>
#include <algorithm>
#include <limits>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
static const ll NEG_INF = std::numeric_limits<ll>::min() / 4;
// 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++) {
v = std::max(v, B.a[i][k] + A.a[k][j]);
}
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 = W.size(), Q = E.size();
// base sum
long long sumA = 0;
for(int i = 0; i < N; i++) sumA += A[i];
if(N == 1) return std::vector<ll>(Q, sumA);
// sort items by weight
struct It{int w, idx;};
std::vector<It> it(N);
for(int i=0;i<N;i++) it[i]={W[i],i};
std::sort(it.begin(), it.end(),[](auto &x,auto &y){return x.w<y.w;});
// compute gaps
std::vector<pair<int,int>> gaps;
for(int k=1;k<N;k++) gaps.emplace_back(it[k].w - it[k-1].w, k);
std::sort(gaps.begin(), gaps.end());
// queries sorted
vector<pair<int,int>> qs(Q);
for(int i=0;i<Q;i++) qs[i]={E[i],i};
sort(qs.begin(), qs.end());
// DSU
vector<int> p(N), sz(N,1);
vector<long long> sumd(N), mind(N);
for(int i=0;i<N;i++){
p[i]=i;
sumd[i] = (long long)A[it[i].idx] - B[it[i].idx];
mind[i] = sumd[i];
}
function<int(int)> find=[&](int x){return p[x]==x?x:p[x]=find(p[x]);};
auto comp_val=[&](int r)->long long{
// matched sum in component: if size even sumd, else sumd - mind
if(sz[r]%2==0) return sumd[r];
else return sumd[r] - mind[r];
};
long long matched=0;
// initially no matches
vector<long long> ans(Q);
int ptr=0;
for(auto &qr:qs){
int D=qr.first, qi=qr.second;
while(ptr<(int)gaps.size() && gaps[ptr].first<=D){
int k=gaps[ptr].second;
int u = find(k-1), v = find(k);
if(u!=v){
// remove old contributions
matched -= comp_val(u);
matched -= comp_val(v);
// unify
p[v]=u;
sz[u]+=sz[v];
sumd[u]+=sumd[v];
mind[u]=min(mind[u], mind[v]);
// add new
matched += comp_val(u);
}
ptr++;
}
ans[qi] = sumA - matched;
}
return ans;
}
