#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
ll mx=10000005,B=4000,lg=24,n;
vi s,p,w,l,dp;
vector<vector<PP>> table;
void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
n=n_;
for(ll x:s_)s.pb(x);
for(ll x:p_)p.pb(x);
for(ll x:w_)w.pb(x);
for(ll x:l_)l.pb(x);
table=vector<vector<PP>>(lg,vector<PP>(n,PP(n,-1,-1)));
rep(i,n){
if(s[i]>B)table[0][i]=PP(l[i],p[i],s[i]);
else table[0][i]=PP(w[i],s[i],inf);
}
rep(i,lg-1)rep(j,n)if(get<0>(table[i][j])!=n){
get<0>(table[i+1][j])=get<0>(table[i][get<0>(table[i][j])]);
get<1>(table[i+1][j])=get<1>(table[i][j])+get<1>(table[i][get<0>(table[i][j])]);
get<2>(table[i+1][j])=min(get<2>(table[i][j]),get<2>(table[i][get<0>(table[i][j])])-get<1>(table[i][j]));
}
dp=vi(n+1);
for(ll i=n-1;i>=0;i--)dp[i]=dp[w[i]]+s[i];
}
long long simulate(int x, int z) {
ll curx=x,curz=z;
while(curx<n&&curz<B){
if(s[curx]<=curz){
curz+=s[curx];curx=w[curx];
}
else{
curz+=p[curx];curx=l[curx];
}
}
if(curx==n)return curz;
while(curx<n&&curz<mx){
for(ll i=lg-1;i>=0;i--)if(get<0>(table[i][curx])<n&&curz<get<2>(table[i][curx])){
curz+=get<1>(table[i][curx]);
curx=get<0>(table[i][curx]);
}
if(s[curx]<=curz){
curz+=s[curx];curx=w[curx];
}
else{
curz+=p[curx];curx=l[curx];
}
}
return dp[curx]+curz;
}
