#include "bits/stdc++.h"
#include "nile.h"
#define pb push_back
using namespace std;
#define ll long long
const ll inf = 1e16;
const int N = 1e5 + 5;
vector<ll> GA(N), GB(N);
struct node{
int l, r;
ll dp[3][3]; // sol sag skip
int go[2][2]; // go[i. adamdan][j + 1 uzunlugunda sola]
node(){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
dp[i][j] = inf;
}
}
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
go[i][j] = 0;
}
}
l = 0, r = 0;
}
};
node merge(node &a, node &b){
node res = node();
for(int l = 0; l < 3; l++){
for(int r = 0; r < 3; r++){
if(l + r > (a.r - a.l + 1) + (b.r - b.l + 1)) continue;
if(l + r == (a.r - a.l + 1) + (b.r - b.l + 1)){
res.dp[l][r] = 0;
continue;
}
if(r >= (b.r - b.l + 1)){
res.dp[l][r] = min(res.dp[l][r], a.dp[l][r - (b.r - b.l + 1)]);
continue;
}
if(l >= (a.r - a.l + 1)){
res.dp[l][r] = min(res.dp[l][r], b.dp[l - (a.r - a.l + 1)][r]);
continue;
}
res.dp[l][r] = min(res.dp[l][r], a.dp[l][0] + b.dp[0][r]);
if(b.go[0][0]) res.dp[l][r] = min(res.dp[l][r], a.dp[l][1] + (GB[a.r] + GB[b.l]) + b.dp[1][r]);
if(b.go[0][1] && a.l < a.r) res.dp[l][r] = min(res.dp[l][r], a.dp[l][2] + (GB[a.r-1] + GA[a.r] + GB[b.l]) + b.dp[1][r]);
if(b.go[1][1]) res.dp[l][r] = min(res.dp[l][r], a.dp[l][1] + (GB[a.r] + GA[b.l] + GB[b.l+1]) + b.dp[2][r]);
}
}
res.l = a.l;
res.r = b.r;
res.go[0][0] = a.go[0][0];
res.go[0][1] = a.go[0][1];
if(a.l < a.r){
res.go[1][0] = a.go[1][0];
res.go[1][1] = a.go[1][1];
}
else{
res.go[1][0] = b.go[0][0];
res.go[1][1] = b.go[0][1];
}
return res;
}
struct SEGT{
vector<node> tree;
void init(int n){
tree.assign(4*n, node());
}
void build(int ind, int l, int r){
if(l == r){
tree[ind].l = l;
tree[ind].r = r;
tree[ind].dp[0][0] = GA[l];
tree[ind].dp[1][0] = tree[ind].dp[0][1] = 0;
}
else{
int m = (l + r)/2;
build(ind*2, l, m);
build(ind*2+1, m+1, r);
tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
}
}
void update(int ind, int l, int r, int pos, int posi){
if(l == r){
tree[ind].go[0][posi] = 1;
}
else{
int m = (l + r)/2;
if(pos <= m) update(ind*2, l, m, pos, posi);
else update(ind*2+1, m+1, r, pos, posi);
tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
}
}
};
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int n = W.size();
vector<array<ll, 3> > art(n);
for(int i = 0; i < n; i++){
art[i] = {W[i], A[i], B[i]};
}
sort(art.begin(), art.end());
for(int i = 1; i <= n; i++){
GA[i] = art[i-1][1];
GB[i] = art[i-1][2];
}
int q = E.size();
vector<ll> ans(q);
vector<pair<ll, ll> > query(q);
for(int i = 0; i < q; i++){
query[i] = {E[i], i};
}
sort(query.begin(), query.end());
vector<array<ll, 3> > upd;
for(int i = 0; i < n; i++){
if(i > 0) upd.pb({art[i][0] - art[i-1][0], i+1, 0});
if(i > 1) upd.pb({art[i][0] - art[i-2][0], i+1, 1});
}
sort(upd.begin(), upd.end());
int updind = 0;
SEGT seg;
seg.init(n);
seg.build(1, 1, n);
for(int qt = 0; qt < q; qt++){
ll d = query[qt].first;
while(updind < upd.size() && upd[updind][0] <= d){
seg.update(1, 1, n, upd[updind][1], upd[updind][2]);
updind++;
}
ans[query[qt].second] = seg.tree[1].dp[0][0];
}
return ans;
}
