#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
vector<int> s,p,w,l;
vector<vector<int>> lift;
vector<vector<long long>> liftcost;
vector<vector<long long>> liftneed;
int n;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
::n=n;
::s=s;
::p=p;
::w=w;
::l=l;
lift = vector(n+1,vector(24,0));
liftcost = vector(n+1,vector(24,0ll));
liftneed = vector(n+1,vector(24,0ll));
for(int i=0;i<n;i++){
lift[i][0] = w[i];
liftcost[i][0] = s[i];
liftneed[i][0] = s[i];
}
liftcost[n][0]=INF;
liftneed[n][0]=INF;
lift[n][0]=n;
for(int bit=1;bit<24;bit++){
for(int i=0;i<=n;i++){
lift[i][bit]=lift[lift[i][bit-1]][bit-1];
liftcost[i][bit]=liftcost[i][bit-1]+liftcost[lift[i][bit-1]][bit-1];
liftneed[i][bit]=max(liftneed[i][bit-1],liftneed[lift[i][bit-1]][bit-1]-liftcost[i][bit-1]);
}
}
return;
}
long long simulate(int x,int z){
while(x!=n){
for(int bit=23;bit>=0;bit--){
if(z>=liftneed[x][bit]){
z+=liftcost[x][bit];
x=lift[x][bit];
}
}
if(x==n)return z;
z += p[x];
x = l[x];
}
return z;
}
