#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int S[400005];
int P[400005];
int W[400005];
int L[400005];
int N;
vector<long long> cutoff;
int parent[400005][25][6];
long long cost[400005][25][6];
const long long INF = 1LL << 62;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
cutoff.push_back(0);
cutoff.push_back(INF);
for(int i = 0; i < N; i ++){
S[i] = s[i];
P[i] = p[i];
W[i] = w[i];
L[i] = l[i];
cutoff.push_back(S[i]);
}
sort(cutoff.begin(), cutoff.end());
cutoff.erase(unique(cutoff.begin(), cutoff.end()), cutoff.end());
assert((int)cutoff.size() <= 7);
while((int)cutoff.size() < 7){
cutoff.push_back(INF);
}
for(int j = 0; j < 6; j ++){
for(int i = 0; i < N; i ++){
parent[i][0][j] = (cutoff[j] >= S[i]) ? W[i] : L[i];
cost[i][0][j] = (cutoff[j] >= S[i]) ? S[i] : P[i];
}
parent[N][0][j] = -1;
}
for(int j = 0; j < 6; j ++){
for(int k = 1; k < 25; k ++){
for(int i = 0; i <= N; i ++){
if(parent[i][k-1][j] == -1){
parent[i][k][j] = -1;
}else{
parent[i][k][j] = parent[parent[i][k-1][j]][k-1][j];
cost[i][k][j] = cost[i][k-1][j] + cost[parent[i][k-1][j]][k-1][j];
}
}
}
}
return;
}
long long op = 0;
long long simulate(int x, int z) {
long long ans = z;
int cur = x;
for(int j = 0; j < 6; j ++){
for(int k = 24; k >= 0; k --){
if(parent[cur][k][j] != -1){
long long tempCost = cost[cur][k][j];
if(ans + tempCost < cutoff[j+1]){
ans += tempCost;
cur = parent[cur][k][j];
}
}
}
if(ans < cutoff[j+1]){
if(parent[cur][0][j] != -1){
ans += cost[cur][0][j];
cur = parent[cur][0][j];
}
}
//printf("ans=%lld; cutoff=%lld\n", ans, cutoff[j]);
}
assert(cur == N);
return ans;
}
