#include "dungeons.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 50000, L = 25; /* L = ceil(log2(10^7 + N)) + 1 */
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int ss[N + 1], pp[N + 1], jjw[N + 1], jjl[N + 1], n;
int jj[L][L][N + 1]; long long dd[L][L][N + 1], upper[L][L][N + 1];
void init(int n_, vi ss_, vi pp_, vi jjw_, vi jjl_) {
int l1, l2, i;
n = n_;
for (i = 0; i < n; i++)
ss[i] = ss_[i], pp[i] = pp_[i], jjw[i] = jjw_[i], jjl[i] = jjl_[i];
for (l1 = 0; l1 < L; l1++) {
for (i = 0; i <= n; i++)
if (i == n)
jj[l1][0][i] = n, dd[l1][0][i] = 0, upper[l1][0][i] = 0;
else if (ss[i] < 1 << l1)
jj[l1][0][i] = jjw[i], dd[l1][0][i] = ss[i], upper[l1][0][i] = INF;
else
jj[l1][0][i] = jjl[i], dd[l1][0][i] = pp[i], upper[l1][0][i] = ss[i];
for (l2 = 1; l2 < L; l2++)
for (i = 0; i <= n; i++) {
int j = jj[l1][l2 - 1][i];
jj[l1][l2][i] = jj[l1][l2 - 1][j];
dd[l1][l2][i] = min(dd[l1][l2 - 1][i] + dd[l1][l2 - 1][j], INF);
upper[l1][l2][i] = max(min(upper[l1][l2 - 1][i], upper[l1][l2 - 1][j] == INF ? INF : upper[l1][l2 - 1][j] - dd[l1][l2 - 1][i]), 0);
}
}
}
long long simulate(int i, int s_) {
int l1, l2;
long long s;
s = s_;
for (l1 = 0; l1 < L && i < n; l1++) {
for (l2 = L - 1; l2 >= 0; l2--)
while (s < upper[l1][l2][i])
s += dd[l1][l2][i], i = jj[l1][l2][i];
if (i < n) {
if (s >= ss[i])
s += ss[i], i = jjw[i];
else
s += pp[i], i = jjl[i];
}
}
return s;
}
