#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vint = vector<int>;
constexpr ll maxn = 400005;
constexpr ll maxphase = 10;
constexpr ll loge = 30;
constexpr int inf = 1e9;
pair<int, pair<int, int>> jump[maxphase][maxn][loge];
ll n;
vll l;
vll p;
vll s;
vll w;
vll pow2;
vll rem(maxn,0);
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n=N;
for(auto num:L)
l.push_back(num);
for(auto num:P)
p.push_back(num);
for(auto num:S)
s.push_back(num);
for(auto num:W)
w.push_back(num);
l.push_back(n);
w.push_back(n);
p.push_back(0);
s.push_back(0);
for(int i=0;i<maxphase;i++)
pow2.push_back(1ll<<i*3);
for(int t=0;t<maxphase;t++)
{
for(int i=0;i<n;i++)
{
if(t>0&&S[i]<=pow2[t-1])
{
jump[t][i][0].first=w[i];
jump[t][i][0].second={s[i],-inf};
}
else
{
jump[t][i][0].first=l[i];
jump[t][i][0].second={p[i],-s[i]};
}
}
}
for(int t=0;t<maxphase;t++)
{
for(int k=1;k<loge;k++)
{
jump[t][N][k].first=N;
jump[t][N][k].second={0,-inf};
for(int i=0;i<n;i++)
{
int nxt=jump[t][i][k-1].first;
jump[t][i][k].first=jump[t][nxt][k-1].first;
jump[t][i][k].second={min(inf,jump[t][i][k-1].second.first+jump[t][nxt][k-1].second.first),max(jump[t][i][k-1].second.second,jump[t][i][k-1].second.first+jump[t][nxt][k-1].second.second)};
}
}
}
rem[n]=0;
for(int i=n-1;i>=0;i--)
rem[i]=rem[w[i]]+s[i];
}
long long simulate(int x, int owo) {
ll strength=owo;
int t=0;
while(x!=n)
{
while(t<maxphase&&pow2[t]<= strength)
t++;
if(t==maxphase)
break;
ll sum=0;
for(int k=loge-1;k>=0;k--)
{
if(sum+jump[t][x][k].second.first<inf&&strength+jump[t][x][k].second.second<0)
{
strength+=jump[t][x][k].second.first;
sum+=jump[t][x][k].second.first;
x=jump[t][x][k].first;
}
}
if(strength>=s[x])
{
strength+=s[x];
x=w[x];
}
else
{
strength+=p[x];
x=l[x];
}
}
return strength+rem[x];
}
