#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
vector<int> s,p,w,l;
vector<vector<vector<int>>> lift;
vector<vector<vector<long long>>> liftcost;
vector<long long> bestans;
vector<int> phases;
int n,phasescnt;
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;
phases = s;
sort(phases.begin(),phases.end());
phases.erase(unique(phases.begin(),phases.end()),phases.end());
phasescnt = phases.size();
lift = vector(5,vector(n+1,vector(24,0)));
liftcost = vector(5,vector(n+1,vector(24,0ll)));
bestans = vector(n+1,0ll);
for(int i=n-1;i>=0;i--){
bestans[i]=bestans[w[i]]+s[i];
for(int phase=0;phase<phasescnt;phase++){
if(s[i]<phases[phase]){
lift[phase][i][0]=w[i];
liftcost[phase][i][0]=s[i];
} else {
lift[phase][i][0]=l[i];
liftcost[phase][i][0]=p[i];
}
}
}
for(int phase=0;phase<phasescnt;phase++){
liftcost[phase][n][0]=INF;
lift[phase][n][0]=n;
}
for(int phase=0;phase<phasescnt;phase++){
for(int bit=1;bit<24;bit++){
for(int i=0;i<=n;i++){
lift[phase][i][bit]=lift[phase][lift[phase][i][bit-1]][bit-1];
liftcost[phase][i][bit]=liftcost[phase][i][bit-1]+liftcost[phase][lift[phase][i][bit-1]][bit-1];
}
}
}
return;
}
long long simulate(int x,int z){
for(int phase=0;phase<phasescnt;phase++){
for(int bit=23;bit>=0;bit--){
if(z+liftcost[phase][x][bit]<phases[phase]){
z+=liftcost[phase][x][bit];
x=lift[phase][x][bit];
}
}
if(x==n)return z;
if(z<phases[phase]){
z+= liftcost[phase][x][0];
x = lift[phase][x][0];
}
}
return z+bestans[x];
}
