#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 3;
const int C = 10000;
const int LOGN = 19;
const ll INF = 1e18;
int n;
vector<int> s, p, w, l;
array<ll, 3> up[LOGN][N]; // pos, strength, max
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n = _n, swap(s, _s), swap(p, _p), swap(w, _w), swap(l, _l);
for(int i = 0; i < n; ++i){
if(s[i] <= C)
up[0][i] = {i, 0, -INF};
else
up[0][i] = {i, 0, -s[i]};
}
for(int j = 1; j < LOGN; ++j){
for(int i = 0; i < n; ++i){
if(up[j - 1][i][0] == n){
up[j][i] = {n, -1, -1};
continue;
}
int a = up[j - 1][i][0], b;
ll add;
if(s[a] <= C){
b = w[a];
add = s[a];
}
else{
b = l[a];
add = p[a];
}
if(b == n || up[j - 1][b][0] == n){
up[j][i] = {n, -1, -1};
continue;
}
up[j][i][0] = up[j - 1][b][0];
up[j][i][1] = up[j - 1][i][1] + add + up[j - 1][b][1];
up[j][i][2] = max(up[j - 1][i][2], up[j - 1][i][1] + add + up[j - 1][b][2]);
}
}
}
long long simulate(int x, int z) {
ll ans = z;
while(ans < C && x != n){
if(ans >= s[x]){
ans += s[x];
x = w[x];
}
else{
ans += p[x];
x = l[x];
}
}
int cnt = 0;
while(x != n){
for(int j = LOGN - 1; j >= 0; --j){
if(up[j][x][0] == n) continue;
if(up[j][x][2] + ans < 0){
ans += up[j][x][1];
x = up[j][x][0];
if(s[x] <= ans){
ans += s[x];
x = w[x];
}
else{
ans += p[x];
x = l[x];
}
if(x == n) return ans;
}
}
if(s[x] <= ans){
ans += s[x];
x = w[x];
}
else{
ans += p[x];
x = l[x];
}
++cnt;
assert(cnt <= 1003);
}
return ans;
}
