#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline void mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline void mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#ifdef DEBUG
#define debug(args...) _debug(args)
inline void _debug(const char* format, ...) {
va_list args;
va_start(args, format);
vprintf(format, args);
va_end(args);
}
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 400005
#define MAXL 30
int n;
vi s, w, l, v;
vll p, r;
bool visited[MAXN];
vi topo;
void getTopo(int u) {
if (!visited[w[u]]) {
visited[w[u]] = 1;
getTopo(w[u]);
}
topo.pb(u);
}
void getTopo1(int u) {
if (!visited[l[u]]) {
visited[l[u]] = 1;
getTopo1(l[u]);
}
topo.pb(u);
}
void init(int _n, vi _s, vi _p, vi _w, vi _l) {
n = _n; s = _s, w = _w, l = _l;
s.pb(0);
_p.pb(0);
w.pb(n);
l.pb(n);
REP (i, 0, n + 1) {
r.pb(s[i]);
p.pb(_p[i]);
}
REP (i, 0, n) {
if (!visited[i]) {
visited[i] = 1;
getTopo(i);
}
}
for (int &i : topo) {
if (i == n) continue;
if (s[w[i]] <= r[i] + s[i]) {
r[i] += r[w[i]];
w[i] = w[w[i]];
}
debug("%d: %d %lld\n", i, w[i], r[i]);
}
topo.clear();
REP (i, 0, n) {
if (!visited[i]) {
visited[i] = 1;
getTopo1(i);
}
}
REP (k, 0, 100) {
for (int &i : topo) {
if (s[l[i]] >= s[i] + p[i]) {
p[i] += p[l[i]];
l[i] = l[l[i]];
}
}
}
}
ll simulate(int x, int z) {
ll ans = z;
while (x != n) {
if (ans >= s[x]) {
ans += r[x];
x = w[x];
} else {
ans += p[x];
x = l[x];
}
}
return ans;
}
