#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 4e5 + 5, logM = 28, limitSZ = logM * (logM + 1) / 2;
const int INF = 0x3c3c3c3c;
struct Data {
int u;
int sum;
int smax;
};
int nn, lose[N], next_win[N], next_los[N], strong[N];
int go_nxt[N];
long long sum_end[N];
int num[logM + 1][logM];
Data pnext[limitSZ][N];
vector<long long> Q;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
nn = n;
REP(i, 0, nn) {
strong[i] = s[i];
lose[i] = p[i];
next_win[i] = w[i];
next_los[i] = l[i];
}
next_win[nn] = nn;
next_los[nn] = nn;
REP(i, 0, nn) go_nxt[i] = next_win[i], sum_end[i] = strong[i];
go_nxt[nn] = nn;
REP(i, 0, 19) {
REP(j, 0, nn) {
sum_end[j] += sum_end[go_nxt[j]];
go_nxt[j] = go_nxt[go_nxt[j]];
}
}
REP(i, 0, logM) Q.push_back(1 << i);
int cnt = 0;
REP(i, 0, logM) REP(j, 0, i) num[i][j] = cnt++;
cerr << cnt;
REP(i, 0, logM) {
REP(j, 0, nn) {
int id = num[i][0];
if (strong[j] < Q[i]) {
pnext[id][j] = {next_win[j], strong[j], INF};
}
else if (strong[j] < Q[i + 1]) {
pnext[id][j] = {next_los[j], lose[j], strong[j]};
}
else {
pnext[id][j] = {next_los[j], lose[j], INF};
}
}
REP(j, 0, i - 1) {
int id = num[i][j];
int id_next = num[i][j + 1];
pnext[id_next][nn] = {0, 0, -1};
REP(w, 0, nn) {
if (pnext[id][w].u == -1) continue;
int wnext = pnext[id][w].u;
Data dnext = {
pnext[id][wnext].u,
pnext[id][w].sum + pnext[id][wnext].sum,
min(pnext[id][w].smax, (pnext[id][wnext].smax == INF ? INF : pnext[id][wnext].smax - pnext[id][w].sum))
};
if (dnext.sum >= INF) dnext.u = -1;
pnext[id_next][w] = dnext;
}
}
}
}
long long simulate(int x, int my_strong) {
REP(i, 0, logM) {
if (my_strong >= Q[i + 1]) continue;
REPD(j, i, 0) {
int id = num[i][j];
Data dnow = pnext[id][x];
if (dnow.u == -1) continue;
if (my_strong + dnow.sum >= Q[i + 1]) continue;
if (my_strong >= dnow.smax) continue;
x = dnow.u;
my_strong += dnow.sum;
}
if (x == nn) break;
if (strong[x] <= my_strong) {
my_strong += strong[x];
x = next_win[x];
}
else {
my_strong += lose[x];
x = next_los[x];
}
assert(my_strong >= Q[i] * 2);
}
return my_strong + sum_end[x];
}
