#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
const int lim = 4e5 + 5;
int n, subtask_id = -1;
vector<int>s, p, w, l;
namespace sub1{
int solve(int x, int z){
while(x < n){
if(z >= s[x]){
z += s[x];
x = w[x];
}
else{
z += p[x];
x = l[x];
}
}
return z;
}
}
struct Data{
int to;
ll need, sum;
Data(){}
Data(int _to, ll _need, ll _sum) : to(_to), need(_need), sum(_sum) {}
};
namespace sub2{
bool check_subtask(){
for(int i = 0; i < n; i++){
if(s[i] != p[i]){
return false;
}
}
return true;
}
vector<Data>up[19];
void init(){
for(int i = 0; i < 19; i++){
up[i].resize(n + 1);
up[i][n] = Data(n, 0, 0);
}
for(int i = 0; i < n; i++){
up[0][i] = Data(w[i], s[i], s[i]);
}
for(int i = 1; i < 19; i++){
for(int j = 0; j < n; j++){
up[i][j].to = up[i - 1][up[i - 1][j].to].to;
up[i][j].need = max(up[i - 1][j].need, up[i - 1][up[i - 1][j].to].need - up[i - 1][j].sum);
up[i][j].sum = up[i - 1][j].sum + up[i - 1][up[i - 1][j].to].sum;
}
}
}
ll solve(int x, ll z){
while(x < n){
for(int bit = 18; bit > -1; bit--){
if(up[bit][x].need <= z){
z += up[bit][x].sum;
x = up[bit][x].to;
}
}
if(x == n){
break;
}
z += p[x];
x = l[x];
}
return z;
}
}
const ll INF = 1e18;
namespace sub34{
bool check_subtask(){
if(n > 50000){
return false;
}
unordered_map<int, bool>cnt;
for(int& x : s){
cnt[x] = true;
if(cnt.size() > 5){
return false;
}
}
return true;
}
vector<ll>val_s;
vector<pair<int, ll>>up[6][24];
int cnt_s;
void init(){
for(int i = 0; i < n; i++){
if(find(val_s.begin(), val_s.end(), s[i]) == val_s.end()){
val_s.push_back(s[i]);
}
}
sort(val_s.begin(), val_s.end());
val_s.push_back(INF);
cnt_s = val_s.size();
for(int i = 0; i < cnt_s; i++){
for(int j = 0; j < 24; j++){
up[i][j].resize(n + 1);
up[i][j][n] = make_pair(n, 0);
}
for(int j = 0; j < n; j++){
bool lose = s[j] >= val_s[i];
up[i][0][j] = make_pair(lose ? l[j] : w[j], lose ? p[j] : s[j]);
}
for(int j = 1; j < 24; j++){
for(int k = 0; k < n; k++){
up[i][j][k].first = up[i][j - 1][up[i][j - 1][k].first].first;
up[i][j][k].second = up[i][j - 1][k].second + up[i][j - 1][up[i][j - 1][k].first].second;
}
}
}
}
ll solve(int x, ll z){
for(int i = 0; i < cnt_s; i++){
for(int bit = 23; bit > -1; bit--){
ll nz = z + up[i][bit][x].second;
if(nz < val_s[i]){
z = nz;
x = up[i][bit][x].first;
}
}
if(x == n){
break;
}
if(z < s[x]){
z += p[x];
x = l[x];
}
else{
z += s[x];
x = w[x];
}
}
return z;
}
}
namespace sub5{
vector<Data>up[25][25];
void init(){
for(int i = 0; i < 25; i++){
for(int j = 0; j < 25; j++){
up[i][j].resize(n + 1);
up[i][j][n] = Data(n, INF, 0);
}
for(int k = 0; k < n; k++){
if(s[k] > (1 << i)){
up[i][0][k] = Data(l[k], s[k] - 1, p[k]);
}
else{
up[i][0][k] = Data(w[k], INF, s[k]);
}
}
for(int j = 1; j < 25; j++){
for(int k = 0; k < n; k++){
up[i][j][k].to = up[i][j - 1][up[i][j - 1][k].to].to;
up[i][j][k].need = min(up[i][j - 1][k].need, up[i][j - 1][up[i][j - 1][k].to].need - up[i][j - 1][k].sum);
up[i][j][k].sum = up[i][j - 1][k].sum + up[i][j - 1][up[i][j - 1][k].to].sum;
}
}
}
}
ll solve(int x, ll z){
for(int i = 0; i < 25; i++){
if(i == 24 || (1 << (i + 1)) > z){
for(int j = 24; j > -1; j--){
if(z <= up[i][j][x].need){
z += up[i][j][x].sum;
x = up[i][j][x].to;
}
}
if(x == n){
break;
}
if(z < s[x]){
z += p[x];
x = l[x];
}
else{
z += s[x];
x = w[x];
}
}
}
return z;
}
}
namespace sub6{
const int lim = 4e5 + 1;
Data up[25][7][lim];
void init(){
for(int i = 0; i < 25; i++){
for(int j = 0; j < 7; j++){
up[i][j][n] = Data(n, INF, 0);
}
for(int k = 0; k < n; k++){
if(s[k] > (1 << i)){
up[i][0][k] = Data(l[k], s[k] - 1, p[k]);
}
else{
up[i][0][k] = Data(w[k], INF, s[k]);
}
}
for(int j = 1; j < 7; j++){
for(int k = 0; k < n; k++){
up[i][j][k] = Data(k, INF, 0);
for(int t = 0; t < 5; t++){
minimize(up[i][j][k].need, up[i][j - 1][up[i][j][k].to].need - up[i][j][k].sum);
up[i][j][k].sum += up[i][j - 1][up[i][j][k].to].sum;
up[i][j][k].to = up[i][j - 1][up[i][j][k].to].to;
}
}
}
}
}
ll solve(int x, ll z){
for(int i = 0; i < 25; i++){
if(i == 24 || (1 << (i + 1)) > z){
for(int j = 6; j > -1; j--){
for(int t = 0; t < 130; t++){
if(z <= up[i][j][x].need){
z += up[i][j][x].sum;
x = up[i][j][x].to;
}
else{
break;
}
}
}
if(x == n){
break;
}
if(z < s[x]){
z += p[x];
x = l[x];
}
else{
z += s[x];
x = w[x];
}
}
}
return z;
}
}
void init(int _n, vector<int>_s, vector<int>_p, vector<int>_w, vector<int>_l){
n = _n;
swap(s, _s);
swap(p, _p);
swap(w, _w);
swap(l, _l);
if(n <= 50000 && max(*max_element(s.begin(), s.end()), *max_element(p.begin(), p.end())) <= 10000){
subtask_id = 1;
}
else if(sub2::check_subtask()){
subtask_id = 2;
sub2::init();
}
else if(sub34::check_subtask()){
subtask_id = 4;
sub34::init();
}
else if(n <= 50000){
subtask_id = 5;
sub5::init();
}
else{
subtask_id = 6;
sub6::init();
}
}
ll simulate(int x, int z){
if(subtask_id == 1){
return sub1::solve(x, z);
}
if(subtask_id == 2){
return sub2::solve(x, z);
}
if(subtask_id == 4){
return sub34::solve(x, z);
}
if(subtask_id == 5){
return sub5::solve(x, z);
}
return sub6::solve(x, z);
}
