#pragma GCC optimize("Ofast")
#include "dungeons.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const int mxn=4e5+5;
const int inf=1e9;
const int k=7;
int N;
vector<int> S,P,W,L;
struct node{
ll sum;
int mn;
int nxt;
};
inline node merge(node &a,node &b){
node c;
c.sum=a.sum+b.sum;
c.nxt=b.nxt;
c.mn=min(a.mn,max(0,(int)(b.mn-a.sum)));
return c;
}
struct graph{
int bound;
node st[mxn][25];
inline void build(int _bound){
bound=_bound;
for(int i=0;i<=N;i++){
st[i][0].nxt=(S[i]>bound?L[i]:W[i]);
st[i][0].sum=(S[i]>bound?P[i]:S[i]);
if(S[i]>bound or i==N){
st[i][0].mn=S[i];
}
else{
st[i][0].mn=inf;
}
}
for(int j=1;j<25;j++){
for(int i=0;i<=N;i++){
st[i][j]=merge(st[i][j-1],st[st[i][j-1].nxt][j-1]);
}
}
}
inline pair<int,ll> solve(int x,ll z){
if(z>=S[x]){
return {x,z};
}
node c;
c.sum=(S[x]>bound?P[x]:S[x]);
c.nxt=(S[x]>bound?L[x]:W[x]);
c.mn=inf;
for(int t=24;t>=0;t--){
int cur=c.nxt;
if(z+c.sum<st[cur][t].mn){
c=merge(c,st[cur][t]);
}
}
int cur=c.nxt;
z+=c.sum;
return make_pair(cur,z);
}
};
graph G[k];
}
void init(int _n, std::vector<int> _S, std::vector<int> _P, std::vector<int> _w, std::vector<int> _l) {
auto st=clock();
N=_n;
S=_S;
P=_P;
W=_w;
L=_l;
S.push_back(0);
P.push_back(0);
W.push_back(N);
L.push_back(N);
for(int i=0;i<k;i++){
G[i].build(1<<(i*3));
}
return;
}
long long simulate(int x, int Z) {
ll z=Z;
//cout<<'\n';
while(x!=N){
int t=min(k-1,(int)__lg(z)/4);
tie(x,z)=G[t].solve(x,z);
if(x==N) return z;
if(z>=S[x]){
z+=S[x];
x=W[x];
}
else{
z+=P[x];
x=L[x];
}
if(x==N) return z;
}
return z;
}
