#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 14;
int n, w[maxn], l[maxn];
ll s[maxn], p[maxn];
vector < int > child[maxn];
struct jump
{
ll sum, best;
int ver;
};
jump dp[maxlog][maxlog][maxn];
bool all_same = true;
set < ll > st;
vector < ll > values;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
n = N;
for (int i = 0; i < n; i ++)
{
s[i] = S[i];
p[i] = P[i];
w[i] = W[i];
l[i] = L[i];
st.insert(s[i]);
child[w[i]].push_back(i);
}
for (auto it : st)
values.push_back(it);
for (int i = 1; i < n; i ++)
{
if (s[i] != s[i - 1])
all_same = false;
}
w[n] = n;
l[n] = n;
for (int k = 0; k < maxlog; k ++)
{
for (int i = 0; i <= n; i ++)
{
if (s[i] >= (1 << (k * 2)))
{
dp[k][0][i].ver = l[i];
dp[k][0][i].best = - s[i];
dp[k][0][i].sum = p[i];
}
else
{
dp[k][0][i].ver = w[i];
dp[k][0][i].best = -1e18;
dp[k][0][i].sum = s[i];
}
}
for (int j = 1; j < maxlog; j ++)
for (int i = 0; i <= n; i ++)
{
dp[k][j][i].ver = dp[k][j - 1][i].ver;
dp[k][j][i].sum = dp[k][j - 1][i].sum;
dp[k][j][i].best = dp[k][j - 1][i].best;
for (int p = 0; p < 3; p ++)
{
dp[k][j][i].best = max(dp[k][j][i].best, dp[k][j - 1][dp[k][j][i].ver].best + dp[k][j][i].sum);
dp[k][j][i].sum = dp[k][j - 1][dp[k][j][i].ver].sum + dp[k][j][i].sum;
dp[k][j][i].ver = dp[k][j - 1][dp[k][j][i].ver].ver;
}
///if (j == 1)
///cout << k << " " << j << " " << i << " " << dp[k][j][i].best << endl;
}
}
return;
}
long long simulate(int x, int z)
{
ll strength = z;
while(x != n)
{
int bit = maxlog - 1;
while(strength < (1 << (bit * 2)))
bit --;
///cout << x << " " << strength << " " << bit << endl;
///cout << x << " :: " << strength << " " << bit << endl;
for (int j = maxlog - 1; j >= 0; j --)
{
for (int p = 0; p < 3; p ++)
if (strength + dp[bit][j][x].best < 0)
{
///cout << j << " --- " << dp[bit][j][x].ver << endl;
strength = strength + dp[bit][j][x].sum;
x = dp[bit][j][x].ver;
}
///else cout << strength << " :::: " << dp[bit][j][x].best << endl;
}
strength = strength + s[x];
x = w[x];
}
return strength;
}
