/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N_MAX = 400000;
const int N_BITS = 25;
const int S_QITS = 13;
int N;
int strength[N_MAX];
int winBonus[N_MAX];
int loseBonus[N_MAX];
int winEdge[N_MAX];
int loseEdge[N_MAX];
int last[S_QITS][N_BITS][N_MAX + 1];
ll bonus[S_QITS][N_BITS][N_MAX + 1];
int maxDiff[S_QITS][N_BITS][N_MAX + 1];
// maximum (bonus - strength) at some moment when we lost
void init (int _N, vector <int> _S, vector <int> _P, vector <int> _W, vector <int> _L) {
// Transfer input to global
N = _N;
for (int u = 0; u < N; u++) {
strength[u] = _S[u];
winBonus[u] = _S[u];
loseBonus[u] = _P[u];
winEdge[u] = _W[u];
loseEdge[u] = _L[u];
}
// Precompute jumps
for (int sqit = 0; sqit < S_QITS; sqit++) {
for (int nbit = 0; nbit < N_BITS; nbit++) {
last[sqit][nbit][N] = N;
bonus[sqit][nbit][N] = 0;
maxDiff[sqit][nbit][N] = INT_MIN;
}
}
for (int u = 0; u < N; u++) {
for (int sqit = 0; sqit < S_QITS; sqit++) {
if ((1 << (sqit * 2)) > strength[u]) {
last[sqit][0][u] = winEdge[u];
bonus[sqit][0][u] = winBonus[u];
maxDiff[sqit][0][u] = INT_MIN;
} else {
last[sqit][0][u] = loseEdge[u];
bonus[sqit][0][u] = loseBonus[u];
maxDiff[sqit][0][u] = 0 - strength[u];
}
}
}
for (int nbit = 1; nbit < N_BITS; nbit++) {
for (int u = 0; u < N; u++) {
for (int sqit = 0; sqit < S_QITS; sqit++) {
int v = last[sqit][nbit - 1][u];
last[sqit][nbit][u] = last[sqit][nbit - 1][v];
bonus[sqit][nbit][u] = bonus[sqit][nbit - 1][u] + bonus[sqit][nbit - 1][v];
ll aux = maxDiff[sqit][nbit - 1][v];
if (aux != INT_MIN) {
aux += bonus[sqit][nbit - 1][u];
}
aux = min((ll) 0, aux);
maxDiff[sqit][nbit][u] = max(maxDiff[sqit][nbit - 1][u], (int) aux);
}
}
}
}
ll simulate (int u, int initStrength) {
ll currStrength = initStrength;
while (u < N) {
int sqit = 0;
while (sqit + 1 < S_QITS && (1 << ((sqit + 1) * 2)) <= currStrength) {
sqit++;
}
for (int nbit = N_BITS - 1; nbit >= 0; nbit--) {
int maxd = maxDiff[sqit][nbit][u];
if (maxd == INT_MIN || currStrength + maxd < 0) {
currStrength += bonus[sqit][nbit][u];
u = last[sqit][nbit][u];
}
}
if (u == N) {
break;
}
if (currStrength >= strength[u]) {
currStrength += winBonus[u];
u = winEdge[u];
} else {
currStrength += loseBonus[u];
u = loseEdge[u];
}
}
return currStrength;
}
