#include <bits/stdc++.h>
using namespace std;
#include "nile.h"
//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
ll s, e, m, val;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
val = 0;
}
void upd(int p, ll v){
if(s == e)val = v;
else{
if(p <= m)l->upd(p, v);
else r->upd(p, v);
val = min(l->val, r->val);
}
}
ll qry(int a, int b){
if(a > b)return 1e18;
if(a == s && b == e)return val;
if(b <= m)return l->qry(a, b);
if(a > m)return r->qry(a, b);
return min(l->qry(a, m), r->qry(m+1, b));
}
}*odd, *even, *ext1, *ext2;
ll cst(int l, int r){
if((r - l + 1) % 2 == 0)return 0;
ll tmp = 1e18;
if(l % 2)tmp = min(odd->qry(l, r), ext2->qry(l + 1, r - 1));
else tmp = min(even->qry(l, r), ext1->qry(l+1, r - 1));
return tmp;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E){
vector <pi> v;
int n = (int)W.size(), q = (int)E.size();
for(int i = 0; i < n; i++)v.push_back({W[i], i});
set <pi> s;
s.insert({0, n - 1});
sort(v.begin(), v.end());
odd = new node(0, n - 1);
even = new node(0, n - 1);
ext1 = new node(0, n - 1);
ext2 = new node(0, n - 1);
for(int i = 0; i < n; i++){
odd->upd(i, 1e18);
even->upd(i, 1e18);
ext1->upd(i, 1e18);
ext2->upd(i, 1e18);
}
for(int i = 0; i < n; i+=2){
even->upd(i, A[v[i].se] - B[v[i].se]);
if(i && i != n - 1)ext2->upd(i, A[v[i].se] - B[v[i].se]);
}
for(int i = 1; i < n; i += 2){
odd->upd(i, A[v[i].se] - B[v[i].se]);
if(i && i != n - 1)ext1->upd(i, A[v[i].se] - B[v[i].se]);
}
vector <pi> Q;
vector <ll> ans; ans.resize(q);
for(int i = 0; i < q; i++)Q.push_back({E[i], i});
sort(Q.begin(), Q.end(), greater<>());
vector <pi> dff, dff2;
for(int i = 1; i < n; i++)dff.push_back({v[i].fi - v[i - 1].fi, i});
for(int i = 2; i < n; i++)dff2.push_back({v[i].fi - v[i - 2].fi, i});
sort(dff.begin(), dff.end(), greater<>());
sort(dff2.begin(), dff2.end(), greater<>());
ll cur = 0;
for(auto i : B)cur += i;
cur += cst(0, n - 1);
int ptr = 0, ptr2 = 0;
// cerr << "ok?\n";
for(auto [i, j] : Q){
while(ptr < n - 1 && dff[ptr].fi > i){
ll tmp = dff[ptr].se;
pi brr = {tmp, 0};
auto it = s.lower_bound(brr);
assert(it != s.begin());
it--;
pi w = *it;
int l = w.fi, r = w.se;
cur -= cst(l, r);
//cerr << tmp << '\n';
if(tmp % 2){
ext1->upd(tmp, 1e18);
ext2->upd(tmp - 1, 1e18);
}
else{
ext1->upd(tmp - 1, 1e18);
ext2->upd(tmp, 1e18);
}
s.erase({l, r});
cur += cst(l, tmp - 1) + cst(tmp, r);
s.insert({l, tmp - 1});
s.insert({tmp, r});
ptr++;
}
//cerr << 1 << '\n';
while(ptr2 < n - 2 && dff2[ptr2].fi > i){
int tmp = dff2[ptr2].se;
pi brr = {tmp, 1e18};
auto it = s.lower_bound(brr);
assert(it != s.begin());
it--;
pi w = *it;
int l = w.fi, r = w.se;
if(l <= tmp - 2 && r >= tmp){
cur -= cst(l, r);
if((tmp - 1) % 2)ext1->upd(tmp - 1, 1e18);
else ext2->upd(tmp - 1, 1e18);
cur += cst(l, r);
}
else {
if((tmp - 1) % 2)ext1->upd(tmp - 1, 1e18);
else ext2->upd(tmp - 1, 1e18);
}
ptr2++;
}
//cerr << 2 << '\n';
ans[j] = cur;
}
return ans;
}
