#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;
vector<long long> bestans;
int n;
bool special_case;
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;
special_case = true;
for(int i=1;i<n;i++)if(s[i]!=s[0])special_case=false;
if(special_case){
lift = vector(n+1,vector(24,0));
liftcost = vector(n+1,vector(24,0ll));
bestans = vector(n+1,0ll);
for(int i=n-1;i>=0;i--){
bestans[i]=bestans[w[i]]+s[i];
lift[i][0] = l[i];
liftcost[i][0] = p[i];
}
liftcost[n][0]=1e8;
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];
}
}
return;
}
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){
if(special_case){
for(int bit=23;bit>=0;bit--){
if(z+liftcost[x][bit]<s[0]){
z+=liftcost[x][bit];
x=lift[x][bit];
}
}
if(x==n)return z;
if(z<s[0]){
z+=liftcost[x][0];
x = lift[x][0];
}
return z+bestans[x];
}
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;
}
