#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
#define sz(x) int((x).size())
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define pb push_back
#define lb lower_bound
#define ub upper_bound
const ll INF = 1e18;
struct Node {
ll best; int idx;
Node() : best(INF), idx(-1) {};
Node(ll v, int i) : best(v), idx(i) {};
Node(Node left, Node right) {
best = min(left.best, right.best);
if (left.best < right.best) idx = left.idx;
else idx = right.idx;
}
};
struct RMQ {
int n; vl arr; vector<Node> st;
RMQ() {};
RMQ(int N, vl Arr) {
n = N; arr = Arr;
st.resize(4*n);
build(0, 0, n);
}
Node build(int i, int l, int r) {
if (l + 1 == r) return st[i] = Node(arr[l], l);
int m = l + (r - l) / 2;
return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
}
Node query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return Node();
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
Node update(int i, int l, int r, int k, ll v) {
if (!(l <= k && k < r)) return st[i];
if (l + 1 == r) return st[i] = Node(v, k);
int m = l + (r - l) / 2;
return st[i] = Node(update(2*i+1, l, m, k, v), update(2*i+2, m, r, k, v));
}
Node query(int l, int r) {
return query(0, 0, n, l, r);
}
void update(int k, ll v) {
update(0, 0, n, k, v);
}
};
vl calculate_costs(vi W, vi A, vi B, vi E) {
int n = sz(W), q = sz(E);
vl w(all(W)), a(all(A)), b(all(B)), e(all(E));
auto rmq = RMQ(n, b);
vl R(q, 0);
FOR(qn, 0, q) {
rmq = RMQ(n, b);
FOR(i, 0, n) {
if (rmq.query(i, i+1).best == INF) continue;
auto best = rmq.query(i+1, i+E[qn]+1);
if (best.best == INF) {
R[qn] += a[i];
// cout << i << " had to go alone\n";
} else {
R[qn] += b[i] + best.best;
rmq.update(best.idx, INF);
rmq.update(i, INF);
// cout << "best for " << i << " is " << best.idx << " with cost " << b[i] + best.best << "\n";
}
}
}
return R;
}
