#include "dungeons.h"
#include <vector>
using namespace std;
typedef long long ll;
pair<int, ll> sp_lose[50002][25], sp_win[50002][25];
pair<int, ll> Plus(pair<int, ll> x, pair<int, ll> y)
{
pair<int, ll> ans;
ans.first = y.first;
ans.second = x.second + y.second;
return ans;
}
int S;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
for(int i=0;i<n;i++) sp_lose[i][0] = {l[i], p[i]};
sp_lose[n][0] = {n, 0};
S = s[0];
for(int t=1;t<=24;t++)
{
for(int i=0;i<=n;i++)
{
int next = sp_lose[i][t-1].first;
sp_lose[i][t] = Plus(sp_lose[i][t-1], sp_lose[next][t-1]);
}
}
for(int i=0;i<n;i++) sp_win[i][0] = {w[i], s[i]};
sp_win[n][0] = {n, 0};
for(int t=1;t<=24;t++)
{
for(int i=0;i<=n;i++)
{
int next = sp_win[i][t-1].first;
sp_win[i][t] = Plus(sp_win[i][t-1], sp_win[next][t-1]);
}
}
return;
}
long long simulate(int x, int z) {
if(z < S)
{
for(int t=24;t>=0;t--)
{
if(sp_lose[x][t].second + z < S)
{
z += sp_lose[x][t].second;
x = sp_lose[x][t].first;
}
}
z += sp_lose[x][0].second;
x = sp_lose[x][0].first;
}
return z + sp_win[x][24].second;
}
