#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
vector<int> s, p, w, l;
bool testcase3, testcase2;
vector<ll> up[30];
vector<ll> upmx[30];
vector<ll> upm[30];
vector<ll> wins;
vector<ll> wup[30];
vector<ll> wupmx[30];
vector<ll> wupm[30];
vector<ll> lup[30];
vector<ll> lupmn[30];
vector<ll> lupm[30];
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n = N;
s = S;
p = P;
w = W;
l = L;
testcase2 = 1;
set<ll> st;
for (int i = 0; i < n; i++) {
if (s[i] != p[i]) {
testcase2 = 0;
}
st.insert(s[i]);
}
if (testcase2) {
for (int i = 0; i < 30; i++) {
up[i].resize(n + 1);
upmx[i].resize(n + 1);
upm[i].resize(n + 1);
if (i == 0) {
for (int j = 0; j < n; j++) {
upm[i][j] = w[j];
up[i][j] = s[j];
upmx[i][j] = s[j] * 2 - up[i][j];
}
upm[i][n] = n;
upmx[i][n] = 0;
up[i][n] = 0;
}
else {
for (int j = 0; j < n + 1; j++) {
upm[i][j] = upm[i - 1][upm[i - 1][j]];
up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]];
upmx[i][j] = max(upmx[i - 1][j], upmx[i - 1][upm[i - 1][j]] - up[i - 1][j]);
}
}
}
}
else if (st.size() == 1) {
testcase3 = 1;
for (int i = 0; i < 30; i++) {
up[i].resize(n + 1);
upm[i].resize(n + 1);
if (i == 0) {
for (int j = 0; j < n; j++) {
upm[i][j] = l[j];
up[i][j] = p[j];
}
upm[i][n] = n;
up[i][n] = 0;
}
else {
for (int j = 0; j < n + 1; j++) {
upm[i][j] = upm[i - 1][upm[i - 1][j]];
up[i][j] = up[i - 1][j] + up[i - 1][upm[i - 1][j]];
}
}
}
// cout << "DEBUG" << endl;
wins.resize(n + 1);
for (int i = n - 1; i >= 0; i--) {
// cout << i << ' ' << s[i] << endl;
wins[i] = s[i] + wins[w[i]];
}
}
for (int i = 0; i < 30; i++) {
wup[i].resize(n + 1);
wupmx[i].resize(n + 1);
wupm[i].resize(n + 1);
lup[i].resize(n + 1);
lupmn[i].resize(n + 1);
lupm[i].resize(n + 1);
if (i == 0) {
for (int j = 0; j < n; j++) {
wupm[i][j] = w[j];
wup[i][j] = s[j];
wupmx[i][j] = s[j] * 2 - wup[i][j];
lupm[i][j] = l[j];
lup[i][j] = p[j];
lupmn[i][j] = s[j];
}
wupm[i][n] = n;
wupmx[i][n] = 0;
wup[i][n] = 0;
lupm[i][n] = n;
lupmn[i][n] = 0;
lup[i][n] = 0;
}
else {
for (int j = 0; j < n + 1; j++) {
wupm[i][j] = wupm[i - 1][wupm[i - 1][j]];
wup[i][j] = wup[i - 1][j] + wup[i - 1][wupm[i - 1][j]];
wupmx[i][j] = max(wupmx[i - 1][j], wupmx[i - 1][wupm[i - 1][j]] - wup[i - 1][j]);
lupm[i][j] = lupm[i - 1][lupm[i - 1][j]];
lup[i][j] = lup[i - 1][j] + lup[i - 1][lupm[i - 1][j]];
lupmn[i][j] = min(lupmn[i - 1][j], lupmn[i - 1][lupm[i - 1][j]] - lup[i - 1][j]);
}
}
}
}
long long simulate2(int x, ll z);
long long simulate3(int x, ll z);
long long simulateult(int x, ll z);
long long simulate(int x, int z) {
return simulateult(x, z);
if (testcase2) {
return simulate2(x, z);
}
if (testcase3) {
return simulate3(x, z);
}
while (x < n) {
if (z >= s[x]) {
z += s[x];
x = w[x];
}
else {
z += p[x];
x = l[x];
}
// cout << x << ' ' << z << '\n';
}
return z;
}
long long simulate2(int x, ll z) {
while (x < n) {
for (int i = 29; i >= 0; i--) {
// cout << i << ' ' << up[i][x] << '\n';
if (upmx[i][x] <= z) {
z += up[i][x];
x = upm[i][x];
}
}
if (x != n) {
z += p[x];
x = l[x];
}
}
return z;
}
long long simulate3(int x, ll z) {
for (int i = 29; i >= 0; i--) {
// cout << i << ' ' << up[i][x] << '\n';
if (z + up[i][x] < s[0] && upm[i][x] != n) {
// cout << z + up[i][x] << '\n';
z += up[i][x];
x = upm[i][x];
// cout << x << ' ' << z << '\n';
}
}
if (z < s[0]) {
z += p[x];
x = l[x];
}
// cout << x << ' ' << z << '\n';
z += wins[x];
// cout << n << ' ' << z << '\n';
return z;
}
long long simulateult(int x, ll z) {
// cout << x << endl;
while (x < n) {
// cout << x << ' ' << z << '\n';
if (z >= s[x]) {
for (int i = 29; i >= 0; i--) {
// cout << i << ' ' << wupmx[i][x] << '\n';
if (wupmx[i][x] <= z) {
z += wup[i][x];
x = wupm[i][x];
}
}
}
else {
for (int i = 29; i >= 0; i--) {
// cout << i << ' ' << lupmn[i][x] << '\n';
if (lupmn[i][x] > z) {
z += lup[i][x];
x = lupm[i][x];
}
}
}
}
return z;
}
