#include "nile.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int N;
struct minseg {
ll tree[404040];
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = 1e18;
return;
}
int mid = (st+ed)/2;
init(2*v, st, mid);
init(2*v+1, mid+1, ed);
tree[v] = min(tree[2*v], tree[2*v+1]);
}
void update(int v, int st, int ed, int idx, ll val) {
if (st > idx || ed < idx) return;
if (st == idx && ed == idx) {
tree[v] = min(tree[v], val);
return;
}
int mid = (st+ed)/2;
update(2*v, st, mid, idx, val);
update(2*v+1, mid+1, ed, idx, val);
tree[v] = min(tree[2*v], tree[2*v+1]);
}
ll get(int v, int st, int ed, int lt, int rt) {
if (lt > ed || rt < st) return 1e18;
if (lt <= st && ed <= rt) return tree[v];
int mid = (st+ed)/2;
return min(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
}
} o1, o2, e1, e2;
vector<pll> C;
ll block(int st, int ed, int D) { // [st, ed]
if ((ed-st)%2 == 1) return 0;
if (st%2) return min(o1.get(1, 0, N-1, st, ed), e2.get(1, 0, N-1, st, ed));
else return min(e1.get(1, 0, N-1, st, ed), o2.get(1, 0, N-1, st, ed));
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int Q = (int)E.size();
N = (int)W.size();
ll sum = 0;
for (int i = 0; i < N; i++) sum += B[i];
vector<ll> R(Q, sum);
for (int i = 0; i < N; i++) C.push_back({W[i], A[i]-B[i]});
sort(C.begin(), C.end());
o1.init(1, 0, N-1);
e1.init(1, 0, N-1);
for (int i = 0; i < N; i++) {
if (i%2) o1.update(1, 0, N-1, i, C[i].second);
else e1.update(1, 0, N-1, i, C[i].second);
}
for (int t = 0; t < Q; t++) {
o2.init(1, 0, N-1);
e2.init(1, 0, N-1);
ll D = E[t];
for (int i = 1; i < N-1; i++) {
if (W[i+1] - W[i-1] > D) continue;
if (i%2) o2.update(1, 0, N-1, i, C[i].second);
else e2.update(1, 0, N-1, i, C[i].second);
}
int st = 0;
while (st < N) {
for (int i = st+1; i <= N; i++) {
if (i == N || C[i].first - C[i-1].first > D) {
R[t] += block(st, i-1, D);
st = i;
break;
}
}
}
}
return R;
}
