#include<bits/stdc++.h>
#include <vector>
using namespace std;
const long long N = 400010;
const long long LOGN = 30;
struct Binary_Lifting{
long long pai[N][LOGN], val[N][LOGN], mx[N][LOGN];
void build(long long n){
for(long long bit = 1;bit < LOGN;bit++){
for(long long i = 0;i <= n;i++){
pai[i][bit] = pai[pai[i][bit-1]][bit-1];
val[i][bit] = val[i][bit-1] + val[pai[i][bit-1]][bit-1];
mx[i][bit] = max(mx[i][bit-1], -val[i][bit-1]+mx[pai[i][bit-1]][bit-1]);
}
}
}
} bin;
map <int, int> comprimir;
long long pai_ruim[N], val_ruim[N];
int n;
void init(int nn, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
n = nn;
vector <array <int, 5>> sortar;
for(int i = 0;i < n;i++){
sortar.push_back({s[i], p[i], w[i], l[i], i});
}
sort(sortar.begin(), sortar.end());
int con = 0;
for(auto [a, b, c, d, i] : sortar){
comprimir[i] = con;
con++;
}
comprimir[con] = con;
con++;
for(auto &[a, b, c, d, i] : sortar){
// cout << i << ' ' << comprimir[i] << '\n';
c = comprimir[c];
d = comprimir[d];
pai_ruim[comprimir[i]] = d;
val_ruim[comprimir[i]] = b;
}
bin.pai[0][0] = sortar[0][2];
bin.val[0][0] = sortar[0][0];
bin.mx[0][0] = sortar[0][0];
for(int i = 1;i < n;i++){
if(sortar[i][2] > i){
bin.pai[i][0] = sortar[i][2];
bin.val[i][0] = sortar[i][0];
bin.mx[i][0] = sortar[i][0];
}
else{
int p = sortar[i][2];
int v = sortar[i][0];
v += bin.val[p][0];
p = bin.pai[p][0];
bin.pai[i][0] = p;
bin.val[i][0] = v;
bin.mx[i][0] = sortar[i][0];
}
}
bin.pai[n][0] = n;
bin.val[n][0] = 0;
bin.mx[n][0] = -1e18;
bin.build(n);
}
long long simulate(int st, int z) {
long long res = z;
st = comprimir[st];
// cout << st << '\n';
while(st != n){
for(int bit = LOGN-1;bit >= 0;bit--){
if(res >= bin.mx[st][bit]){
// cout << st << '\n';
// cout << bit << ' ' << st << ' ' << res << ' ' << bin.pai[st][bit] << ' ' << bin.mx[st][bit] << '\n';
res += bin.val[st][bit];
st = bin.pai[st][bit];
}
}
if(st == n) break;
res += val_ruim[st];
st = pai_ruim[st];
}
return res;
}
