#include "nile.h"
#include <vector>
#include <array>
#include <set>
#include <tuple>
#include <algorithm>
using namespace std;
using ll = long long;
vector<ll> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E) {
vector<tuple<int, int, int> > a;
int n = (int)W.size(), q = (int)E.size();
for (int i = 0; i < n; ++i) a.emplace_back(W[i], A[i], B[i]);
sort(a.begin(), a.end());
for (int i = 0; i < n; ++i) tie(W[i], A[i], B[i]) = a[i];
ll base = 0, added = 0;
for (int i = 0; i < n; ++i) base += B[i];
vector<pair<int, int> > gap1, gap2;
for (int i = 1; i < n; ++i) gap1.emplace_back(W[i] - W[i - 1], i - 1);
for (int i = 2; i < n; ++i) gap2.emplace_back(W[i] - W[i - 2], i - 2);
sort(gap1.begin(), gap1.end(), greater<>());
sort(gap2.begin(), gap2.end(), greater<>());
vector<pair<int, int> > E1;
for (int i = 0; i < q; ++i) E1.emplace_back(E[i], i);
sort(E1.begin(), E1.end());
vector<ll> ans(q);
struct Blk {
int l, r; ll pr[2], jmp;
bool operator<(const Blk&o) const { return r < o.r; }
ll cost() { return (l ^ r) % 2 ? 0ll : min({jmp, pr[l & 1]}); }
};
set<Blk> st;
const ll oo = 1e18;
for (int i = 0; i < n; ++i) {
Blk b = {i, i, {oo, oo}, oo};
b.pr[i & 1] = A[i] - B[i];
st.insert(b);
added += b.cost();
}
for (auto [QrE, QrEi] : E1) {
while (gap1.size() && gap1.back().first <= QrE) {
auto i = gap1.back().second; gap1.pop_back();
auto it = st.lower_bound({0, i, {0, 0}, 0}), it2 = next(it);
auto b = *it, bRig = *it2;
st.erase(it); st.erase(it2);
added -= b.cost() + bRig.cost();
b.r = bRig.r;
for (auto x : {0, 1}) b.pr[x] = min(b.pr[x], bRig.pr[x]);
b.jmp = min(b.jmp, bRig.jmp);
st.insert(b);
added += b.cost();
}
while (gap2.size() && gap2.back().first <= QrE) {
auto i = gap2.back().second; gap2.pop_back();
auto it = st.lower_bound({0, i, {0, 0}, 0});
ll cst = A[i + 1] - B[i + 1];
if (it->jmp > cst) {
auto b = *it; added -= b.cost(); b.jmp = cst;
st.erase(it); st.insert(b);
added += b.cost();
}
}
ans[QrEi] = base + added;
}
return ans;
}
