#include "nile.h"
#include<bits/stdc++.h>
#define c custo
using namespace std;
const int N = 200010;
long long dp[N];
long long custo[N];
long long w[N];
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();
long long sum = 0;
vector <array <int, 3>> ordenar;
for(int i = 0;i < n;i++){
ordenar.push_back({W[i], A[i], B[i]});
}
sort(ordenar.begin(), ordenar.end());
for(int i = 0;i < n;i++){
w[i+1] = ordenar[i][0];
sum += (long long) (ordenar[i][1]);
custo[i+1] = ordenar[i][1] - ordenar[i][2];
}
vector <long long> resposta;
for(auto d : E){
long long res = 0;
vector <pair <long long, long long>> intervalos;
intervalos.push_back({w[1], custo[1]});
for(int i = 2;i <= n;i++){
if(w[i] - w[i-1] > d){
long long soma = intervalos[0].second;
long long mn = intervalos[0].second;
int tam = intervalos.size();
for(int j = 1;j < intervalos.size();j++){
soma += intervalos[j].second;
if(j%2 == 0){
mn = min(mn, intervalos[j].second);
}
else if(j+1 != tam){
if(intervalos[j+1].first - intervalos[j-1].first <= d){
mn = min(mn, intervalos[j].second);
}
}
}
res += soma - (tam%2 == 1 ? mn : 0);
intervalos.clear();
intervalos.push_back({w[i], custo[i]});
}
else{
intervalos.push_back({w[i], custo[i]});
}
}
long long soma = intervalos[0].second;
long long mn = intervalos[0].second;
int tam = intervalos.size();
for(int j = 1;j < intervalos.size();j++){
soma += intervalos[j].second;
if(j%2 == 0){
mn = min(mn, intervalos[j].second);
}
else if(j+1 != tam){
if(intervalos[j+1].first - intervalos[j-1].first <= d){
mn = min(mn, intervalos[j].second);
}
}
}
res += soma - (tam%2 == 1 ? mn : 0);
resposta.push_back(sum-res);
}
return resposta;
}
