#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef tuple<ll,ll,ll> PP;
typedef vector<PP> vpp;
typedef vector<vpp> vvpp;
#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 pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
ll n;
vi s,p,w,l;
vvpp table;
PP f(PP a,PP b){
chmax(get<1>(a),get<1>(b)-get<2>(a));
get<2>(a)+=get<2>(b);
get<0>(a)=get<0>(b);
return a;
}
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_){
n=n_+1;
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);
s.pb(0);p.pb(0);w.pb(n-1);l.pb(n-1);
table=vvpp(20,vpp(n));
rep(i,n)table[0][i]=PP(w[i],s[i],s[i]);
rep(i,19)rep(j,n)table[i+1][j]=f(table[i][j],table[i][get<0>(table[i][j])]);
return;
}
long long simulate(int x_, int z_) {
ll i=x_,cur=z_;
/*
while(i<n-1){
if(cur>=s[i]){
cur+=s[i];
i=w[i];
}
else{
cur+=p[i];
i=l[i];
}
}
*/
while(i<n-1){
if(cur<s[i]){
cur+=p[i];i=l[i];
}
else{
PP tmp(i,0,0);
for(ll j=19;j>=0;j--){
auto ntmp=f(tmp,table[j][get<0>(tmp)]);
if(get<1>(ntmp)<=cur){
tmp=ntmp;
}
}
i=get<0>(tmp);cur+=get<2>(tmp);
}
}
return cur;
}
