#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using int64 = long long;
#define pi pair<int64, int64>
#define artefak pair<pi, pi>
const int64 inf = -(1 << 40);
const int64 mxn = (1 << 18);
int64 tree[4*mxn];
void update(int n, int l, int r, int idx, int val){
if(l == r){
tree[n] = val;
return;
}
int m = (l+r)/2;
if(idx <= m){
update(2*n+1, l, m, idx, val);
}else update(2*n+2, m+1, r, idx, val);
tree[n] = max(tree[2*n+1], tree[2*n+2]);
}
int64 query(int n, int lf, int rg, int l, int r){
if(r < lf || rg < l) return inf;
if(lf <= l && rg <= r) return tree[n];
int mid = (lf+rg)/2;
return max(query(2*n+1, lf, mid, l, r), query(2*n+2, mid+1,rg, l,r));
}
vector<int64> calculate_costs(vector<int> w,vector<int> a, vector<int> b, vector<int> e){
int n = w.size(), q = e.size();
if(n == 0){
return vector<int64>(q, 0);
}
int sigma_a = 0;
vector<artefak> item;
for(int i = 0;i < n; i++){
sigma_a += a[i];
item.push_back({{w[i], a[i]}, {b[i], a[i]-b[i]}});
}
bool cek = 1;
sort(item.begin(), item.end());
for(auto &lo : item){
if(lo.fi.se != 2 || lo.se.fi != 1){
cek = 0;
break;
}
}
vector<int64> ans;
if(cek){
for(int d : e){
vector<int> dp(n);
int j = 0;
for(int i = 1; i <n; i++){
while(j < i && item[j].fi.fi < item[i].fi.fi-d) j++;
int ambil = 0;
if(j <= i-1){
ambil = dp[i] = 1+(i-2>=0 ? dp[i-2] : 0);
}
dp[i] = max(dp[i-1], ambil);
}
int m = dp[n-1];
ans.push_back(2*n-2*m);
}
return ans;
}
for(int i = 0; i < q; i++){
int d = e[i];
fill(tree, tree+4*n, inf);
update(0, 0, n-1, 0, item[0].se.se);
vector<int64> dp(n);
for(int j = 1; j < n; j++){
int W = item[j].fi.fi;
int minw = W-d;
int l = 0, r = j;
while(l < r){
int mid = (l+r)>>1;
if(item[mid].fi.fi < minw) l = mid+1;
else r = mid;
}
int jnt = l;
int64 ambil = inf;
if(jnt <= j-1){
ambil = item[j].se.se+query(0,0,n-1, jnt, j-1);
}
dp[j] = dp[j-1];
if(ambil >= -1e15) dp[j] = max(dp[j], ambil);
int64 val = item[j].se.se+dp[j-1];
update(0,0,n-1,j,val);
}
int64 sav = dp[n-1];
int64 cost = sigma_a-sav;
ans.push_back(cost);
}
return ans;
}
