#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=400050;
const int L=24;
const int K=8;
const ll inf=(ll)1e18;
int n,nxt[K][L][N],S[N],W[N];
ll pw[K+5],sum[K][L][N],mn[K][L][N],ft[N];
vector<pair<int,int>> E[N];
void DFS(int u,ll tot){
ft[u]=tot;
for(auto e:E[u])DFS(e.first,tot+e.second);
}
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
::n=n;for(int i=0;i<n;i++)S[i]=s[i],W[i]=w[i];W[n]=n;S[n]=0;
pw[0]=1;for(int i=1;i<=K;i++)pw[i]=pw[i-1]*8;
for(int i=0;i<K;i++){
int h=pw[i];
nxt[i][0][n]=n;
sum[i][0][n]=0;
mn[i][0][n]=inf;
for(int j=0;j<n;j++){
if(s[j]<=h){
nxt[i][0][j]=w[j];
sum[i][0][j]=s[j];
mn[i][0][j]=inf;
}else{
nxt[i][0][j]=l[j];
sum[i][0][j]=p[j];
mn[i][0][j]=s[j];
}
}
for(int j=1;j<L;j++)for(int l=0;l<=n;l++){
nxt[i][j][l]=nxt[i][j-1][nxt[i][j-1][l]];
sum[i][j][l]=min(inf,sum[i][j-1][l]+sum[i][j-1][nxt[i][j-1][l]]);
mn[i][j][l]=min(mn[i][j-1][l],mn[i][j-1][nxt[i][j-1][l]]-sum[i][j-1][l]);
}
}
for(int i=0;i<n;i++)E[w[i]].push_back({i,s[i]});
DFS(n,0);
}
ll simulate(int x,int z){
ll h=z;
for(int i=0;i<K;i++){
while(1){
if(h>=pw[i+1]||x==n)break;
for(int j=L-1;j>=0;j--){
if(mn[i][j][x]>h){
h+=sum[i][j][x];
x=nxt[i][j][x];
}
}
h+=S[x];x=W[x];
}
}
return h+ft[x];
}
