#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int D = 7;
const int LOG = 25;
const int N = 4e5 + 5;
int n;
int nxt[D][LOG][N];
long long d[D][LOG][N];
vector<int> s, p, w, l;
vector<long long> strengths;
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_;
strengths.push_back(0);
for (int i = 0; i < n; ++i) {
strengths.push_back(s[i]);
}
sort(strengths.begin(), strengths.end());
strengths.resize(unique(strengths.begin(), strengths.end()) - strengths.begin());
strengths.push_back(LLONG_MAX);
for (int itr = 0; itr < (int) strengths.size(); ++itr) {
int cur_strength = strengths[itr];
d[itr][0][n] = 0;
nxt[itr][0][n] = n;
for (int i = 0; i < n; ++i) {
if (cur_strength >= s[i]) {
d[itr][0][i] = s[i];
nxt[itr][0][i] = w[i];
} else {
d[itr][0][i] = p[i];
nxt[itr][0][i] = l[i];
}
}
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i <= n; ++i) {
d[itr][j][i] = d[itr][j - 1][i] + d[itr][j - 1][nxt[itr][j - 1][i]];
nxt[itr][j][i] = nxt[itr][j - 1][nxt[itr][j - 1][i]];
}
}
}
return;
}
long long simulate(int x, int z) {
long long strength = z;
while (x != n) {
int itr = 0;
for (int j = (int) strengths.size() - 1; j >= 0; --j) {
if (strength >= strengths[j]) {
itr = j;
break;
}
}
for (int j = LOG - 1; j >= 0; --j) {
if (strength + d[itr][j][x] < strengths[itr + 1]) {
strength += d[itr][j][x];
x = nxt[itr][j][x];
}
}
if (x == n) {
return strength;
}
if (strength >= s[x]) {
strength += s[x];
x = w[x];
} else {
strength += p[x];
x = l[x];
}
}
return strength;
}
