#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], limit[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;
collect[n][j] = 0;
limit[n][j] = 0;
}
for (int i = n-1; i >= 0; -- i)
{
jump[i][0] = win[i];
collect[i][0] = a[i];
limit[i][0] = a[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];
limit[i][j] = max(limit[i][j-1], limit[jump[i][j-1]][j-1] - collect[i][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);
}
pair < long long, long long > stimulate_losing(int pos, long long power)
{
if(power >= a[pos])return make_pair(pos, power);
return stimulate_losing(lose[pos], power + b[pos]);
}
long long simulate(int x, int z)
{
long long pos = x, power = z;
while(pos != nn)
{
// cout << pos << " " << power << endl;
for (int bit = 29; bit >= 0; -- bit)
{
if(jump[pos][bit] > pos && limit[pos][bit] <= power)
{
// cout << "movingggg " << endl;
power += collect[pos][bit];
pos = jump[pos][bit];
}
}
if(pos == nn)return power;
pair < long long, long long > op = stimulate_losing(pos, power);
pos = op.first;
power = op.second;
}
return power;
}
/***
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
*/
