#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
int nn;
int ss;
vector<vector<pair<int,ll>>> bl;
vector<ll> last;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
ss = s[0];
bl.resize(31, vector<pair<int,ll>>(n+1));
bl[0][n] = {n,0};
for(int i = 0; i < n; i++) bl[0][i] = {l[i], p[i]};
for(int i = 1; i < 31; i++) for(int j = 0; j <= n; j++) bl[i][j] = {bl[i-1][bl[i-1][j].F].F, bl[i-1][j].S+bl[i-1][bl[i-1][j].F].S};
last.resize(n+1,0);
for(int i = n-1; i+1; i--) last[i] = last[w[i]] + s[0];
/*for(int i = 0; i < 4; i++) {
for(int j = 0; j <= n; j++) cout << "(" << bl[i][j].F << ", " << bl[i][j].S << ") ";
cout << endl;
}*/
}
ll simulate(int x, int z) {
ll k = z;
for(int i = 30; i+1; i--) if(k+bl[i][x].S < ss) k += bl[i][x].S, x = bl[i][x].F;
//cout << "k: " << x << " " << k << endl;
if(k < ss) k += bl[0][x].S, x = bl[0][x].F;
return k+last[x];
}
