#include "dungeons.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int maxn = 4e5 + 10;
int nn;
vector < long long > a, b;
vector < long long > win, lose;
long long req, jump[maxn][30], collect[maxn][30];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
nn = n;
a.resize(n, 0);
b.resize(n, 0);
req = s[0];
for (int i = 0; i < nn; ++ i)
a[i] = s[i];
for (int i = 0; i < nn; ++ i)
b[i] = p[i];
win.resize(n, 0);
lose.resize(n, 0);
for (int i = 0; i < nn; ++ i)
win[i] = w[i];
for (int i = 0; i < nn; ++ i)
lose[i] = l[i];
for (int j = 0; j < 30; ++ j)
{
jump[n][j] = n;
}
for (int i = 0; i < n; ++ i)
{
jump[i][0] = lose[i];
collect[i][0] = b[i];
}
for (int j = 1; j < 30; ++ j)
{
for (int i = 0; i < n; ++ i)
{
jump[i][j] = jump[jump[i][j-1]][j-1];
collect[i][j] = collect[i][j-1] + collect[jump[i][j-1]][j-1];
}
}
}
bool check(long long start, long long s, long long x)
{
long long pos = start, power = s;
for (int i = 29; i >= 0; -- i)
{
if((1 << i) & x)
{
power += collect[pos][i];
pos = jump[pos][i];
if(pos == nn)return 1;
if(power >= req)return 1;
}
}
return (power >= req);
}
long long rec(long long pos, long long s)
{
if(pos == nn)return s;
if(s >= a[pos])return rec(win[pos], s+a[pos]);
else return rec(lose[pos], s+b[pos]);
}
long long simulate(int x, int z)
{
long long lt = 0, rt = 1e7, mid, ans = 1e7+1;
while(lt <= rt)
{
mid = (lt + rt)/2;
if(check(x, z, mid))
{
rt = mid - 1;
ans = mid;
}
else lt = mid + 1;
}
assert(ans < 1e7+1);
long long pos = x, power = z;
for (int bit = 0; bit < 30; ++ bit)
{
if((1 << bit) & ans)
{
assert(pos != nn);
pos = jump[pos][bit];
power += collect[pos][bit];
}
}
return rec(pos, power);
}
