#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LOG1 = 9; // 8^i를 기준
const int LOG2 = 25;
const long long INF = 1e18;
int nxt[LOG1][LOG2][400010];
ll sum[LOG1][LOG2][400010];
ll lmt[LOG1][LOG2][400010];
ll ex[LOG1];
int N;
vector <int> S, P, W, L;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N=n, S=s, P=p, W=w, L=l;
int i, j, k;
ex[0] = 1;
for (i=1; i<LOG1; i++){
ex[i] = ex[i-1]*8;
}
for (i=0; i<LOG1; i++){
for (j=0; j<n; j++){
if (ex[i] >= S[j]){
if (W[j]==n){
nxt[i][0][j] = -1;
}
else{
nxt[i][0][j] = W[j];
sum[i][0][j] = S[j];
lmt[i][0][j] = INF;
}
}
else{
if (L[j]==n){
nxt[i][0][j] = -1;
}
else{
nxt[i][0][j] = L[j];
sum[i][0][j] = P[j];
lmt[i][0][j] = S[j];
}
}
}
}
for (i=0; i<LOG1; i++){
for (j=1; j<LOG2; j++){
for (k=0; k<n; k++){
if (nxt[i][j-1][k]==-1 || nxt[i][j-1][nxt[i][j-1][k]]==-1){
nxt[i][j][k]=-1;
}
else{
nxt[i][j][k] = nxt[i][j-1][nxt[i][j-1][k]];
sum[i][j][k] = sum[i][j-1][k] + sum[i][j-1][nxt[i][j-1][k]];
lmt[i][j][k] = min(lmt[i][j-1][k], lmt[i][j-1][nxt[i][j-1][k]] - sum[i][j-1][k]);
}
}
}
}
return;
}
long long simulate(int x, int z) {
ll str = z;
int i, lv=0;
while(x!=N){
while (lv+1<LOG1 && str>=ex[lv+1]){
lv++;
}
for (i=LOG2-1; i>=0; i--){
if (nxt[lv][i][x]==-1) continue;
if (str>=lmt[lv][i][x]) continue;
str += sum[lv][i][x];
x = nxt[lv][i][x];
}
if (str>=S[x]){
str += S[x];
x = W[x];
}
else{
str += P[x];
x = L[x];
}
}
return str;
}
