#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
const ll LINF = 1e18;
int n;
int max_log = 62;
vector<vi> up;
vector<vll> h, mx;
vll s, p, w, l;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = N;
s.assign(S.begin(), S.end());
p.assign(P.begin(), P.end());
w.assign(W.begin(), W.end());
l.assign(L.begin(), L.end());
s.push_back(LINF); p.push_back(0); w.push_back(n); l.push_back(n);
up.assign(n + 1, vi(max_log + 1));
h.assign(n + 1, vll(max_log + 1));
mx.assign(n + 1, vll(max_log + 1));
for (int i = 0; i <= n; i++) {
up[i][0] = w[i];
h[i][0] = p[i];
mx[i][0] = s[i];
}
for (int j = 1; j <= max_log; j++) {
for (int i = 0; i <= n; i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
h[i][j] = h[i][j - 1] + h[up[i][j - 1]][j - 1];
mx[i][j] = max(mx[i][j - 1], mx[up[i][j - 1]][j - 1] - h[i][j - 1]);
}
}
}
long long simulate(int x, int z) {
ll ans = z;
while (x != n) {
for (int i = max_log; i >= 0; i--) {
if (ans >= mx[x][i]) {
ans += h[x][i];
x = up[x][i];
}
}
if (ans >= s[x]) {
ans += p[x];
x = w[x];
}
ans += p[x];
x = l[x];
}
return ans;
}
