#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mxN=50050;
const ll INF=1000000000;
ll N, K;
ll S[mxN], P[mxN], W[mxN], L[mxN];
pll adj[mxN];
vector <ll> coor;
pll sps[mxN][30][6];
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];
for(int i=0;i<N;i++) coor.push_back(S[i]);
sort(coor.begin(), coor.end());
coor.erase(unique(coor.begin(), coor.end()), coor.end());
K=coor.size();
sort(coor.begin(), coor.end());
for(int i=0;i<N;i++) adj[i]={L[i], P[i]};
adj[N]={N, 0};
for(int i=0;i<=K;i++)
{
for(int j=0;j<=N;j++) sps[j][0][i]=adj[j];
for(int j=1;j<30;j++)
{
for(int k=0;k<=N;k++)
{
sps[k][j][i].fir=sps[sps[k][j-1][i].fir][j-1][i].fir;
sps[k][j][i].sec=sps[sps[k][j-1][i].fir][j-1][i].sec+sps[k][j-1][i].sec;
}
}
if(i==K) break;
for(int j=0;j<N;j++)
{
if(S[j]<=coor[i]) adj[j]={W[j], S[j]};
else adj[j]={L[j], P[j]};
}
}
return;
}
long long simulate(int x, int z) {
ll ans=z;
for(int i=0;i<K;i++)
{
if(ans>=coor[i]) continue;
for(int j=29;j>=0;j--)
{
if(sps[x][j][i].sec+ans>=coor[i]) continue;
ans+=sps[x][j][i].sec;
x=sps[x][j][i].fir;
}
if(x==N) return ans;
ans+=sps[x][0][i].sec;
x=sps[x][0][i].fir;
if(x==N) return ans;
}
ans+=sps[x][29][K].sec;
return ans;
}
