#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
// editorial
const int N = 50001;
int n;
int s[N];
int p[N];
int w[N];
int l[N];
vector<vector<int>> nxt[25];
vector<vector<int>> lim[25];
vector<vector<int>> inc[25];
/*
int nxt[25][25][N];
int lim[25][25][N];
int inc[25][25][N];
*/
long long d[N];
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
for (int i = 0; i < 25; i++) {
nxt[i] = vector<vector<int>>(i + 1, vector<int>(N));
lim[i] = vector<vector<int>>(i + 1, vector<int>(N));
inc[i] = vector<vector<int>>(i + 1, vector<int>(N));
}
n = n_;
for (int i = 0; i < n; i++) {
s[i] = s_[i];
p[i] = p_[i];
w[i] = w_[i];
l[i] = l_[i];
}
for (int i = n - 1; i >= 0; i--) {
d[i] = d[w[i]] + s[i];
}
for (int i = 0; i < 25; i++) {
for (int x = 0; x < n; x++) {
if (s[x] >= (1 << i)) {
nxt[i][0][x] = l[x];
lim[i][0][x] = max(0, min((1 << (i + 1)) - p[x], s[x]));
inc[i][0][x] = p[x];
} else {
nxt[i][0][x] = w[x];
lim[i][0][x] = (1 << (i + 1)) - s[x];
inc[i][0][x] = s[x];
}
}
nxt[i][0][n] = n;
for (int j = 1; j <= i; j++) {
nxt[i][j][n] = n;
for (int x = 0; x < n; x++) {
int y = nxt[i][j - 1][x];
nxt[i][j][x] = nxt[i][j - 1][y];
lim[i][j][x] = max(0, min(lim[i][j - 1][x], lim[i][j - 1][y] - inc[i][j - 1][x]));
inc[i][j][x] = min(1 << 27, inc[i][j - 1][x] + inc[i][j - 1][y]);
}
}
}
}
long long simulate(int x, int z) {
long long res = z;
for (int i = 0; i < 25; i++) {
if (x == n) {
break;
}
if (res < (1 << i)) {
if (res >= s[x]) {
res += s[x];
x = w[x];
} else {
res += p[x];
x = l[x];
}
}
assert(res >= (1 << i));
for (int j = i; j >= 0; j--) {
if (lim[i][j][x] > res) {
res += inc[i][j][x];
x = nxt[i][j][x];
}
}
}
res += d[x];
return res;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
debug(simulate(0, 1)); // 24
debug(simulate(2, 3)); // 25
return 0;
}
#endif
