#include <bits/stdc++.h>
using namespace std;
const int oo = 1 << 30;
template<typename T>
struct SegmentTree
{
int low, mid, high;
T value;
SegmentTree *l, *r;
SegmentTree(int low, int high, vector<T> &initial): low(low), high(high)
{
mid = (low + high) / 2;
if (low == high)
{
l = r = NULL;
value = initial[low];
}
else
{
l = new SegmentTree(low, mid, initial);
r = new SegmentTree(mid + 1, high, initial);
value = min(l->value, r->value);
}
}
void update(int x, T v)
{
if (low == high)
{
value = v;
return;
}
if (x <= mid) l->update(x, v);
else r->update(x, v);
value = min(l->value, r->value);
}
T get(int x, int y)
{
if (low == x && high == y)
return value;
if (y <= mid) return l->get(x, y);
else if (x > mid) return r->get(x, y);
else return min(l->get(x, mid), r->get(mid + 1, y));
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e)
{
int n = size(w);
long long curAns = accumulate(begin(a), end(a), 0LL);
vector<pair<int, int>> c;
for (int i = 0; i < n; i++)
c.push_back({w[i], a[i] - b[i]});
sort(begin(c), end(c));
vector<pair<int, int>> diffs;
for (int i = 0; i < n - 1; i++)
{
diffs.push_back({c[i + 1].first - c[i].first, i});
if (i < n - 2)
diffs.push_back({c[i + 2].first - c[i].first, i + n - 1});
}
sort(begin(diffs), end(diffs));
set<int> active;
for (int i = -1; i < n; i++)
active.insert(i);
vector<int> odd, even;
for (int i = 0; i < n; i++)
if (i % 2)
{
odd.push_back(c[i].second);
even.push_back(oo);
}
else
{
odd.push_back(oo);
even.push_back(c[i].second);
}
SegmentTree<int> oddTree(0, n - 1, odd);
SegmentTree<int> evenTree(0, n - 1, even);
map<int, long long> ansMap;
ansMap[-1] = curAns;
auto getScore = [&](int i)
{
auto u = active.lower_bound(i);
int r = *u;
u--;
int l = *u + 1;
int len = r - l + 1;
if (len % 2 == 0)
return 0;
return l % 2 ? oddTree.get(l, r) : evenTree.get(l, r);
};
for (int i = 0; i < size(diffs);)
{
auto [curDiff, _] = diffs[i];
int j = i;
while (j < size(diffs))
{
auto [d, id] = diffs[j];
if (d > curDiff)
break;
if (id < n - 1)
{
curAns -= getScore(id) + getScore(id + 1);
active.erase(id);
curAns += getScore(id);
}
else
{
id -= n - 1;
curAns -= getScore(id);
if (id % 2) oddTree.update(id + 1, c[id + 1].second);
else evenTree.update(id + 1, c[id + 1].second);
curAns += getScore(id);
}
j++;
}
i = j;
ansMap[curDiff] = curAns;
}
vector<long long> ans;
for (int d : e)
{
auto it = ansMap.upper_bound(d);
it--;
ans.push_back(it->second);
}
return ans;
}
