#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 lose[N][21]; //lose[i][k] = dungeon that is 2^k losses from i
int sum[N][21]; //sum[i][k] = total stregnth gained correspondingly
int lim[N][21]; //lim[i][k] = max strength limit
int win[N];
void twok(){
for(int i=0; i<n; i++){
lose[i][0] = l[i];
sum[i][0] = p[i];
lim[i][0] = s[i];
}
lose[n][0] = n;
for(int k=1; k<21; k++){
for(int i=0; i<=n; i++){
int p = lose[i][k-1];
lose[i][k] = lose[p][k-1];
sum[i][k] = sum[i][k-1] + sum[p][k-1];
lim[i][k] = min(lim[i][k-1], lim[p][k-1] - sum[i][k-1]);
}
}
}
void findnext(int &x, int &z){
for(int k=20; k>=0; k--){
if(lim[x][k] <= z) continue;
z += sum[x][k];
x = lose[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();
win[n] = 0;
for(int i=n-1; i>=0; i--) win[i] = win[w[i]] + s[i];
return;
}
long long simulate(signed X, signed Z) {
int x = X, z = Z;
findnext(x,z);
if(x == n) return z;
else return z + win[x];
}
