#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<17;
int fau[N], mi[N][2], l[N], r[N];
int cst[N]; ll cans = 0LL;
pair<int, int> joi[N];
pair<int, int> upd[N];
pair<int, int> tab[N];
pair<int, int> que[N];
vector<ll> answer;
int Find(int v)
{
if(fau[v] == v) return v;
return (fau[v] = Find(fau[v]));
}
inline void Calc(int a)
{
cst[a] = 0;
if(l[a] % 2 == r[a] % 2)
cst[a] += mi[a][l[a] % 2];
}
void Union(int a, int b)
{
a = Find(a); b = Find(b);
cans -= (ll)(cst[a] + cst[b]);
fau[b] = a;
mi[a][0] = min(mi[a][0], mi[b][0]);
mi[a][1] = min(mi[a][1], mi[b][1]);
r[a] = r[b];
Calc(a);
cans += (ll)cst[a];
}
void Upd(int v)
{
int x = tab[v].nd;
v = Find(v);
mi[v][0] = min(mi[v][0], x);
mi[v][1] = min(mi[v][1], x);
cans -= (ll)cst[v];
Calc(v);
cans += (ll)cst[v];
}
void Ans(int n, int q)
{
for(int i = 1; i <= n; ++i)
{
mi[i][0] = II; mi[i][1] = II;
mi[i][i % 2] = tab[i].nd;
l[i] = i; r[i] = i; fau[i] = i;
Calc(i);
cans += cst[i];
if(i < n)
joi[i] = make_pair(tab[i + 1].st - tab[i].st, i);
if(i > 1 && i < n)
upd[i - 1] = make_pair(tab[i + 1].st - tab[i - 1].st, i);
}
//cerr << "Init: " << cans << "\n";
if(n > 1)
sort(joi + 1, joi + 1 + (n - 1));
if(n > 2)
sort(upd + 1, upd + 1 + (n - 2));
int j1 = 0, j2 = 0;
for(int i = 1; i <= q; ++i)
{
while(j1 < n - 1 && joi[j1 + 1].st <= que[i].st)
{
++j1;
Union(joi[j1].nd, joi[j1].nd + 1);
}
while(j2 < n - 2 && upd[j2 + 1].st <= que[i].st)
{
++j2;
Upd(upd[j2].nd);
}
answer[que[i].nd] += cans;
}
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int>E)
{
int n = W.size(), q = E.size();
ll bans = 0LL;
for(int i = 1; i <= n; ++i)
{
tab[i] = make_pair(W[i - 1], (ll)(A[i - 1] - B[i - 1]));
bans += B[i - 1];
}
for(int i = 0; i < q; ++i)
{answer.pb(bans); que[i + 1] = make_pair(E[i], i);}
sort(tab + 1, tab + 1 + n);
sort(que + 1, que + 1 + q);
Ans(n, q);
return answer;
}
