#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
lld S[1000000];
lld P[1000000];
lld W[1000000];
lld L[1000000];
pair<int,lld> STL[1000000][32];
lld NW[1000000];
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N=n;
rep(i,0,n){
S[i]=s[i];
P[i]=p[i];
W[i]=w[i];
L[i]=l[i];
}
L[n]=n;
P[n]=0;
NW[n]=0;
for(int i=n-1;i>-1;i--){
NW[i]=NW[W[i]]+S[i];
}
rep(i,0,n+1){
STL[i][0]={L[i],P[i]};
STL[i][0].second=min(STL[i][0].second,S[i]);
}
for(int j=1;j<32;j++){
rep(i,0,n+1){
STL[i][j]={STL[STL[i][j-1].first][j-1].first,STL[STL[i][j-1].first][j-1].second+STL[i][j-1].second};
STL[i][j].second=min(STL[i][j].second,S[i]);
}
}
}
#define DEBUG 0
lld Simulate(int x, lld z){
if(x==N)return z;
for(int j=31;j>-1;j--){
if(STL[x][j].second+z<S[x]){
z+=STL[x][j].second;
x=STL[x][j].first;
return Simulate(x,z);
}
}
if(z<S[x]){
return Simulate(L[x],z+P[x]);
}else{
return z+NW[x];
}
}
long long simulate(int x, int z) {
if(DEBUG){
//cout<<x<<" "<<z<<endl;
if(x==N)return z;
if(z<S[x])return simulate(L[x],z+P[x]);
return simulate(W[x],z+S[x]);
}
return Simulate(x,z);
}
