#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=4e5+5;
const ll LOG=21;
const ll inf=1e18;
const ll dumb=6;
ll n;
ll s[mxN], p[mxN], w[mxN], l[mxN];
array<ll, 2> up[mxN][LOG][dumb]; // des, sum
vll con;
ll siz;
array<ll, 2> mrg(array<ll, 2> a, array<ll, 2> b){
array<ll, 2> re;
re[0]=b[0];
re[1]=a[1]+b[1];
return re;
}
array<ll, 3> mrg2(array<ll, 3> a, array<ll, 3> b){
array<ll, 3> re;
re[0]=b[0];
re[1]=min(a[1], b[1]-a[2]);
re[2]=a[2]+b[2];
return re;
}
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n=N;
for(ll i=0;i<=n;i++){
s[i]=S[i];
p[i]=P[i];
w[i]=W[i];
l[i]=L[i];
}
for(ll i=0;i<n;i++){
con.pb(s[i]);
}
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
siz=con.size();
for(ll i=0;i<=siz;i++){
if(i<siz){
for(ll j=0;j<n;j++){
if(s[j]<con[i]){
up[j][0][i]={w[j], s[j]};
}
else{
up[j][0][i]={l[j], p[j]};
}
}
up[n][0][i]={n, 0};
}
else{
for(ll j=0;j<n;j++){
up[j][0][i]={w[j], s[j]};
}
up[n][0][i]={n, 0};
}
}
for(ll k=0;k<=siz;k++){
for(ll j=1;j<LOG;j++){
for(ll i=0;i<=n;i++){
up[i][j][k]=mrg(up[i][j-1][k], up[up[i][j-1][k][0]][j-1][k]);
}
}
}
}
long long simulate(int x, int z) {
// cout<<"qrying "<<x<<' '<<z<<'\n';
ll ans=z;
while(x!=n){
// cout<<"ans: "<<ans<<'\n';
// cout<<"x: "<<x<<'\n';
ll lev=0;
for(ll i=0;i<siz;i++){
if(ans>=con[i]) lev=i+1;
}
ll thr=inf;
if(lev<siz){
thr=con[lev];
}
// cout<<"lev: "<<lev<<'\n';
// cout<<"thr: "<<thr<<'\n';
for(ll i=LOG-1;i>=0;i--){
if(ans+up[x][i][lev][1]<thr){
// cout<<"going\n";
ans+=up[x][i][lev][1];
x=up[x][i][lev][0];
// cout<<"ans: "<<ans<<'\n';
// cout<<"x: "<<x<<'\n';
}
}
// cout<<"ans: "<<ans<<'\n';
// cout<<"x: "<<x<<'\n';
ans+=up[x][0][lev][1];
x=up[x][0][lev][0];
}
// cout<<"ans: "<<ans<<'\n';
// cout<<"x: "<<x<<'\n';
return ans;
}
