#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
int n, tot, mxS;
const int mxN = (int)4e5+10;
const int mxLg = 25;
vi S, w, l,s,p;
struct jmpNode{
int loc;
ll totSt;
int mxSt;
jmpNode(int x=-1, ll y=0){
loc=x, totSt=y; mxSt=y;
}
};
jmpNode jmp[mxLg][mxN];
void init(int N, vi s, vi p, vi w, vi l) {
n = N; mxS = max(*max(all(s)),*max(all(p)));
::w = w, ::l = l, ::p=p, ::s=s;
for(int i = 0; i < n; i++)
jmp[0][i] = jmpNode(w[i],s[i]);
jmp[0][n]= jmpNode(n,0);
for(int i = 1; i < mxLg; i++){
for(int j = 0; j < n; j++){
jmp[i][j].loc = jmp[i-1][jmp[i-1][j].loc].loc;
jmp[i][j].totSt = jmp[i-1][j].totSt+jmp[i-1][jmp[i-1][j].loc].totSt;
jmp[i][j].mxSt = max(jmp[i-1][j].mxSt,jmp[i-1][jmp[i-1][j].loc].mxSt);
}
jmp[i][n] = jmpNode(n,0);
}
}
ll simulate(int x, int z) {
ll strength = z;
while(x!=n and strength<mxS){
if(s[x]>strength) strength+=p[x], x=l[x];
else strength+=s[x], x=w[x];
int curStr = strength;
for(int i = mxLg-1; i>=0 and strength<mxS; i--){
if(jmp[i][x].loc!=n and jmp[i][x].mxSt<=curStr)
strength+=jmp[i][x].totSt, x=jmp[i][x].loc;
}
if(x!=n) strength+=jmp[0][x].totSt, x=jmp[0][x].loc;
}
for(int i = mxLg-1; i>=0; i--)
if(jmp[i][x].loc!=n)
strength+=jmp[i][x].totSt, x=jmp[i][x].loc;
if(x!=n) strength+=jmp[0][x].totSt, x=jmp[0][x].loc;
return strength;
}
