#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace ns{
int n,m;
int s[400005],p[400005],w[400005],l[400005];
int toe[400005];
//int f[21][400005],g[21][400005],h[21][400005];
struct arr{
signed v[400005];
signed &operator [](int b){return v[b];}
};
arr tb[505],*f[12],*g[12],*h[12],*las=tb;
arr *neww(int n){
arr *ret=las;las+=n;return ret;
}
int a[400005];
const signed inf=0x3f3f3f3f;
int pw[25];
void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
n=N;
for(int i=0;i<n;++i)s[i]=S[i],p[i]=P[i],w[i]=W[i],l[i]=L[i];
/*for(int i=0;i<n;++i)a[i+1]=s[i];
sort(a+1,a+n+1);
m=unique(a+1,a+n+1)-a-1;
for(int v=0;v<=m;++v){
for(int i=0;i<n;++i){
f[v][0][i]=(s[i]<=a[v]?w[i]:l[i]);
g[v][0][i]=(s[i]<=a[v]?s[i]:p[i]);
}
f[v][0][n]=n;g[v][0][n]=0;
for(int i=1;i<=30;++i)for(int j=0;j<=n;++j){
f[v][i][j]=f[v][i-1][f[v][i-1][j]];
g[v][i][j]=g[v][i-1][j]+g[v][i-1][f[v][i-1][j]];
}
}*/
for(int i=n-1;~i;--i)toe[i]=s[i]+toe[w[i]];
for(int i=0;i<=12;++i)pw[i]=1<<(i+i);
for(int v=0;v<12;++v){
f[v]=neww(v+v+2);
g[v]=neww(v+v+2);
h[v]=neww(v+v+2);
for(int i=0;i<n;++i){
if(s[i]<pw[v]){
f[v][0][i]=w[i];
g[v][0][i]=s[i];
h[v][0][i]=inf;
}
else{
f[v][0][i]=l[i];
g[v][0][i]=p[i];
h[v][0][i]=s[i];
}
}
f[v][0][n]=n;g[v][0][n]=0;h[v][0][n]=inf;
for(int i=1;i<=v+v+1;++i){
for(int j=0;j<=n;++j){
f[v][i][j]=f[v][i-1][f[v][i-1][j]];
g[v][i][j]=min(g[v][i-1][j]+g[v][i-1][f[v][i-1][j]],inf);
h[v][i][j]=max(min(h[v][i-1][j],h[v][i-1][f[v][i-1][j]]-g[v][i-1][j]),-1);
}
}
}
/*for(int i=0;i<n;++i){
f[0][i]=w[i],g[0][i]=s[i],h[0][i]=s[i];
}
f[0][n]=n;g[0][n]=h[0][n]=0;
for(int i=1;i<=20;++i){
for(int j=0;j<=n;++j){
f[i][j]=f[i-1][f[i-1][j]];
g[i][j]=max(g[i-1][j],g[i-1][f[i-1][j]]-h[i-1][j]);
h[i][j]=h[i-1][j]+h[i-1][f[i-1][j]];
}
}*/
}
long long simulate(int x, int z) {
int rk=0;
while(x<n){
if(z>=pw[rk+1]&&rk<12)++rk;
if(rk==12){
return z+toe[x];
}
for(int i=rk+rk+1;~i;--i){
if(z<h[rk][i][x] && g[rk][i][x]+z<pw[rk+1]){
z+=g[rk][i][x];
x=f[rk][i][x];
}
}
if(x<n){
if(z>=s[x]){
z+=s[x];x=w[x];
}
else{
z+=p[x];x=l[x];
}
}
}
return z;
/*while(x<n){
for(int i=20;~i;--i){
if(z>=g[i][x]){
z+=h[i][x];
x=f[i][x];
}
}
if(x<n){
z+=p[x];x=l[x];
}
}*/
/* if(z>=s[x]){
z+=s[x];x=w[x];
}
else{
z+=p[x];x=l[x];
}
}*/
return z ;
}
}
void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
ns::init(N,S,P,W,L);
}
long long simulate(signed x, signed z) {
return ns::simulate(x,z);
}
