#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 4e5 + 10;
const int lg = 20;
const int st = 5;
const int inf = 1e9;
int n, s[maxn], p[maxn], w[maxn], l[maxn];
int par[lg][lg][maxn];
int mn[lg][lg][maxn];
int sum[lg][lg][maxn];
ll val[maxn];
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
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];
}
w[n] = l[n] = n;
for (int i = 0; i < lg; i++){
for (int k = 0; k <= n; k++){
if (s[k] > (1 << (i+st))){
sum[i][0][k] = p[k];
mn[i][0][k] = s[k];
par[i][0][k] = l[k];
}
else{
sum[i][0][k] = s[k];
mn[i][0][k] = inf;
par[i][0][k] = w[k];
}
}
for (int j = 1; j <= st; j++){
for (int k = 0; k <= n; k++){
int tmp = mn[i][j-1][par[i][j-1][k]];
mn[i][j][k] = min(mn[i][j-1][k], tmp - sum[i][j-1][k]);
mn[i][j][k] = max(mn[i][j][k], 0);
par[i][j][k] = par[i][j-1][par[i][j-1][k]];
sum[i][j][k] = min((int)1e7, sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]]);
}
}
for (int k = 0; k <= n; k++){
sum[i][0][k] = sum[i][st][k];
mn[i][0][k] = mn[i][st][k];
par[i][0][k] = par[i][st][k];
}
for (int j = 1; j < lg; j++){
for (int k = 0; k <= n; k++){
int tmp = mn[i][j-1][par[i][j-1][k]];
mn[i][j][k] = min(mn[i][j-1][k], tmp - sum[i][j-1][k]);
mn[i][j][k] = max(mn[i][j][k], 0);
par[i][j][k] = par[i][j-1][par[i][j-1][k]];
sum[i][j][k] = min((int)1e7, sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]]);
}
}
}
for (int i = n-1; ~i; i--){
val[i] = val[w[i]] + s[i];
}
debug(1);
}
int lst = -1;
ll solve(int x, ll z){
// debug(x, z);
if (x == n) return z;
if (z >= 1e7) return z + val[x];
int ptr = 31 - __builtin_clz(z);
ptr -= st;
ptr = min(ptr, lg-1);
if (ptr == lst) assert(0);
lst = ptr;
//debug(ptr);
int v = x;
ll cnt = z;
for (int i = lg-1; ~i; i--){
// debug(i, v, mn[ptr][i][v], par[ptr][i][v], sum[ptr][i][v], cnt);
if (sum[ptr][i][v] + cnt >= 1e7 || par[ptr][i][v] == n || mn[ptr][i][v] <= cnt) continue;
cnt += sum[ptr][i][v];
v = par[ptr][i][v];
}
//debug(v, cnt);
int tmp = (1 << st);
// debug(0, v, cnt);
while(tmp--){
if (cnt >= s[v]){
cnt += s[v];
v = w[v];
}
else{
cnt += p[v];
v = l[v];
}
}
//debug(1, v, cnt);
return solve(v, cnt);
}
long long simulate(int x, int z) {
lst = -1;
ll cnt = z;
while(x != n && cnt < (1 << st)){
if (cnt >= s[x]){
cnt += s[x];
x = w[x];
}
else{
cnt += p[x];
x = l[x];
}
}
return solve(x, cnt);
}
