#include "nile.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int n, q;
long long w[maxn], a[maxn], b[maxn];
long long dp[maxn]; /// best match count
long long r[maxn];
long long ans;
long long pa[maxn], sz[maxn], res[maxn];
long long best[maxn], bs[maxn];
int find_leader(int i)
{
if(pa[i] == i)return i;
return (pa[i] = find_leader(pa[i]));
}
void unite(int i, int j)
{
i = find_leader(i);
j = find_leader(j);
ans -= res[i];
ans -= res[j];
sz[i] += sz[j];
pa[j] = i;
best[i] = min(best[i], best[j]);
bs[i] += bs[j];
res[i] = bs[i] + best[i];//(sz[i] % 2);
ans += res[i];
}
vector < pair < int, int > > u;
long long solve(int d)
{
vector < pair < int, int > > pack;
pack.pb({w[0], 0});
long long ans = 0;
for (int i = 1; i < n; ++ i)
{
int last = pack[pack.size()-1].first;
if(w[i] - last <= d)
{
pack.pb({w[i], i});
continue;
}
long long sumb = 0, best = 1e17;
for (int j = 0; j < pack.size(); ++ j)
{
int index = pack[j].second;
sumb += b[index];
if(j % 2 == 0)best = min(best, a[index] - b[index]);
else if(j != pack.size()-1)
{
int pre = pack[j-1].first;
int nxt = pack[j+1].first;
if(nxt - pre <= d)best = min(best, a[index] - b[index]);
}
}
ans += sumb;
if(pack.size() % 2 == 1)ans += best;
pack.clear();
pack.pb({w[i], i});
}
long long sumb = 0, best = 1e17;
for (int j = 0; j < pack.size(); ++ j)
{
int index = pack[j].second;
sumb += b[index];
if(j % 2 == 0)best = min(best, a[index] - b[index]);
else if(j != pack.size()-1)
{
int pre = pack[j-1].first;
int nxt = pack[j+1].first;
if(nxt - pre <= d)best = min(best, a[index] - b[index]);
}
}
ans += sumb;
if(pack.size() % 2 == 1)ans += best;
pack.clear();
return ans;
/*vector < pair < int, int > > g;
for (int i = 1; i < n; ++ i)
{
int d = w[i] - w[i-1];
g.push_back(make_pair(d, i-1));
}
sort(g.begin(), g.end());
int i = 0;
for (auto &[dif, pos]: u)
{
while(i < g.size() && g[i].first <= dif)
{
int posx = g[i].second;
int posy = posx + 1;
unite(posx, posy);
i ++;
}
r[pos] = ans;
}*/
}
struct p
{
int w, a, b;
p(){};
p(int _w, int _a, int _b)
{
w = _w;
a = _a;
b = _b;
}
};
bool cmp(p p1, p p2)
{
return (p1.w < p2.w);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E)
{
n = W.size();
for (int i = 0; i < n; ++ i)
w[i] = W[i];
for (int i = 0; i < n; ++ i)
a[i] = A[i];
for (int i = 0; i < n; ++ i)
b[i] = B[i];
vector < p > g;
for (int i = 0; i < n; ++ i)
g.pb(p(w[i], a[i], b[i]));
sort(g.begin(), g.end(), cmp);
int i = 0;
for (auto &[ww, aa, bb]: g)
{
w[i] = ww;
a[i] = aa;
b[i] = bb;
i ++;
}
for (int i = 0; i < n; ++ i)
{
pa[i] = i;
sz[i] = 1;
res[i] = a[i];
bs[i] = b[i];
best[i] = a[i] - b[i];
ans += a[i];
}
q = (int)E.size();
vector < long long > result;
for (int i = 0; i < q; ++ i)
{
result.pb(solve(E[i]));
}
return result;
}
