#include<bits/stdc++.h>
#include <vector>
using namespace std;
const long long N = 400010;
const long long LOGN = 20;
struct Binary_Lifting{
long long pai[N][LOGN], val[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];
}
}
}
} bin[6];
set <long long> valores_s;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
for(long long i = 0;i < n;i++){
valores_s.insert(s[i]);
}
if(valores_s.size() > 5) exit(0);
for(long long i = 0;i < n;i++){
bin[0].pai[i][0] = l[i];
bin[0].val[i][0] = p[i];
}
bin[0].pai[n][0] = n;
bin[0].val[n][0] = 0;
long long con = 1;
for(auto x : valores_s){
for(long long i = 0;i < n;i++){
bin[con].pai[i][0] = (x >= s[i] ? w[i] : l[i]);
bin[con].val[i][0] = (x >= s[i] ? s[i] : p[i]);
}
bin[con].pai[n][0] = n;
bin[con].val[n][0] = 0;
con++;
}
for(long long i = 0;i < con;i++){
bin[i].build(n);
}
return;
}
long long simulate(int st, int z) {
long long res = z;
long long con = 0;
for(auto x : valores_s){
if(res < x){
//cout << 'a' << ' ';
long long dif = x-res;
for(long long bit = LOGN-1;bit >= 0;bit--){
long long p = bin[con].pai[st][bit], v = bin[con].val[st][bit];
if(v >= dif) continue;
st = p;
dif -= v;
res += v;
}
res += bin[con].val[st][0];
st = bin[con].pai[st][0];
}
//cout << res << ' ' << st << '\n';
con++;
}
res += bin[con].val[st][LOGN-1];
return res;
}
