#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;
const int N = 400005;
int n;
vector<signed> s,p,w,l;
int win[N][21]; //win[i][k] = dungeon that is 2^k wins from i
int sum[N][21]; //sum[i][k] = total stregnth gained correspondingly
int req[N][21]; //req[i][k] = min strength required
void twok(){
for(int i=0; i<n; i++){
win[i][0] = w[i];
sum[i][0] = s[i];
req[i][0] = s[i];
}
win[n][0] = n;
for(int k=1; k<21; k++){
for(int i=0; i<=n; i++){
int p = win[i][k-1];
win[i][k] = win[p][k-1];
sum[i][k] = sum[i][k-1] + sum[p][k-1];
req[i][k] = max(req[i][k-1], req[p][k-1] - sum[i][k-1]);
}
}
}
void findnext(int &x, int &z){
for(int k=20; k>=0; k--){
if(req[x][k] > z) continue;
z += sum[x][k];
x = win[x][k];
}
}
void init(signed nn, vector<signed> S, vector<signed> P, vector<signed> W, vector<signed> L) {
n = nn, s = S, p = P, w = W, l = L;
twok();
return;
}
long long simulate(signed X, signed Z) {
int x = X, z = Z;
while(x != n){
findnext(x,z);
if(x != n) z += p[x], x = l[x];
}
return z;
}
