#include "dungeons.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 4e5;
const ll MAXK = 19;
struct path{
ll x,max1,sum;
};
path sp[MAXK][MAXN];
vector <int> s,p,w,l;
ll n;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n=N;
s=S,p=P,w=W,l=L;
for (ll i = 0;i < n;i ++)sp[0][i] = {w[i],s[i],s[i]};
sp[0][n] = {n,0,0};
for (ll j = 1;j < MAXK;j ++){
for (ll i = 0;i <= n;i ++){
sp[j][i].x = sp[j-1][sp[j-1][i].x].x;
sp[j][i].max1 = max(sp[j-1][i].max1,sp[j-1][sp[j-1][i].x].max1);
sp[j][i].sum = sp[j-1][i].sum + sp[j-1][sp[j-1][i].x].sum;
}
}
return;
}
long long simulate(int x, int z) {
while (x!=n){
for (ll j = MAXK-1;j>=0;j--){
if (sp[j][x].max1 <= z){
z += sp[j][x].sum;
x = sp[j][x].x;
}
}
if (x!=n){
z+=p[x];
x=l[x];
}
}
return z;
}
