#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 400001;
const int LOG = 50;
vector<long long> win(MAX_N);
vector<vector<long long>> dist, nxt, mini;
vector<int> s,p,w,l;
int n;
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
ios::sync_with_stdio(false);
cin.tie(0);
s = ss; p = pp; w = ww; l = ll; n = nn;
l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n);
dist.resize(MAX_N, vector<long long>(LOG));
nxt.resize(MAX_N, vector<long long>(LOG));
mini.resize(MAX_N, vector<long long>(LOG));
for (int j = 0; j <= n; j++) {
dist[j][0] = s[j];
nxt[j][0] = w[j];
mini[j][0] = s[j];
}
for (int k = 1; k < LOG; k++){
for (int j = 0; j <= n; j++) {
dist[j][k] = dist[j][k-1] + dist[nxt[j][k-1]][k-1];
nxt[j][k] = nxt[nxt[j][k-1]][k-1];
mini[j][k] = max(mini[j][k-1], mini[nxt[j][k-1]][k-1] - dist[j][k-1]);
}
}
win[n] = 0;
for (int i = n-1; i >= 0; i--) {
win[i] = win[w[i]] + s[i];
}
return;
}
long long simulate(int x, int z) {
long long st = z;
int pos = x;
while (pos != n) {
if (st < s[pos]) {
st += p[pos];
pos = l[pos];
continue;
}
for (int i = LOG-1; i >= 0; i--) {
if (st < mini[pos][i]) continue;
st += dist[pos][i];
pos = nxt[pos][i];
}
st += s[pos];
pos = l[pos];
}
return st;
}
