#include "bits/stdc++.h"
#include "dungeons.h"
using namespace std;
#define ll long long
const int inf = 2e9 + 5;
const int N = 1e6 + 5;
const int K = 24;
vector<vector<int> > nxt, add, jump;
vector<vector<ll> > sum, mx;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
nxt.resize(n+1);
add.resize(n+1);
for(int i = 0; i < n; i++){
nxt[i].resize(2);
nxt[i][0] = l[i];
nxt[i][1] = w[i];
add[i].resize(2);
add[i][0] = p[i];
add[i][1] = s[i];
}
nxt[n].resize(2);
add[n].resize(2);
nxt[n][0] = nxt[n][1] = n;
add[n][0] = add[n][1] = 0;
jump.resize(n+1);
sum.resize(n+1);
mx.resize(n+1);
for(int i = 0; i <= n; i++){
jump[i].resize(K);
sum[i].resize(K);
mx[i].resize(K);
jump[i][0] = nxt[i][1];
sum[i][0] = add[i][1];
mx[i][0] = add[i][1];
}
for(int i = 1; i < K; i++){
for(int j = 0; j <= n; j++){
jump[j][i] = jump[jump[j][i-1]][i-1];
sum[j][i] = sum[j][i-1] + sum[jump[j][i-1]][i-1];
mx[j][i] = max(mx[j][i-1], mx[jump[j][i-1]][i-1] - sum[j][i-1]);
}
}
return;
}
long long simulate(int x, int z){
int n = nxt.size() - 1;
long long cur = z;
while(x != n){
for(int j = K-1; j >= 0; j--){
if(mx[x][j] <= cur){
cur += sum[x][j];
x = jump[x][j];
}
}
if(add[x][1] > cur){
cur += add[x][0];
x = nxt[x][0];
}
}
return cur;
}
