#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 400050;
const int L = 24;
const int K = 8;
const ll inf = (ll)1e18;
int n, nxt[K][L][N], S[N], W[N];
ll pw[K + 5], sum[K][L][N], mn[K][L][N], ft[N];
vector<pair<int, int>> E[N];
void DFS(int u, ll tot) {
ft[u] = tot;
for (auto e : E[u])
DFS(e.first, tot + e.second);
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
::n = n;
for (int i = 0; i < n; i++)
S[i] = s[i], W[i] = w[i];
W[n] = n;
S[n] = 0;
pw[0] = 1;
for (int i = 1; i <= K; i++)
pw[i] = pw[i - 1] * 8;
for (int i = 0; i < K; i++) {
int h = pw[i];
nxt[i][0][n] = n;
sum[i][0][n] = 0;
mn[i][0][n] = inf;
for (int j = 0; j < n; j++) {
if (s[j] <= h) {
nxt[i][0][j] = w[j];
sum[i][0][j] = s[j];
mn[i][0][j] = inf;
} else {
nxt[i][0][j] = l[j];
sum[i][0][j] = p[j];
mn[i][0][j] = s[j];
}
}
for (int j = 1; j < L; j++)
for (int l = 0; l <= n; l++) {
nxt[i][j][l] = nxt[i][j - 1][nxt[i][j - 1][l]];
sum[i][j][l] = min(inf, sum[i][j - 1][l] + sum[i][j - 1][nxt[i][j - 1][l]]);
mn[i][j][l] = min(mn[i][j - 1][l], mn[i][j - 1][nxt[i][j - 1][l]] - sum[i][j - 1][l]);
}
}
for (int i = 0; i < n; i++)
E[w[i]].push_back({i, s[i]});
DFS(n, 0);
}
ll simulate(int x, int z) {
ll h = z;
for (int i = 0; i < K; i++) {
while (1) {
if (h >= pw[i + 1] || x == n)
break;
for (int j = L - 1; j >= 0; j--) {
if (mn[i][j][x] > h) {
h += sum[i][j][x];
x = nxt[i][j][x];
}
}
h += S[x];
x = W[x];
}
}
return h + ft[x];
}
