#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dungeon
{
int n; ll sum, x;
dungeon() : dungeon(0, 0, 0) {}
dungeon(int _n, ll _s, ll _x) : n(_n), sum(_s), x(_x) {}
} sp[400002][21];
struct dungeon_lose
{
int n; ll sum, x;
dungeon_lose() : dungeon_lose(0, 0, 0){}
dungeon_lose(int _n, ll _s, ll _x) : n(_n), sum(_s), x(_x) {}
} sp_lose[400002][21];
dungeon f(dungeon x, dungeon y)
{
dungeon ans;
ans.n = y.n;
ans.sum = x.sum + y.sum;
ans.x = max(x.x, y.x - x.sum);
return ans;
}
dungeon_lose f_lose(dungeon_lose x, dungeon_lose y)
{
dungeon_lose ans;
ans.n = y.n;
ans.sum = x.sum + y.sum;
ans.x = min(x.x, y.x - x.sum);
return ans;
}
int N;
vector<int> L, P, S, W;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
L = l;
P = p;
S = s;
W = w;
for(int i=0;i<n;i++)
sp[i][0] = dungeon(w[i], s[i], s[i]);
sp[n][0] = dungeon(n, 0, 0);
for(int t=1;t<=20;t++)
{
for(int i=0;i<=n;i++)
{
int next = sp[i][t-1].n;
sp[i][t] = f(sp[i][t-1], sp[next][t-1]);
}
}
for(int i=0;i<n;i++)
sp_lose[i][0] = dungeon_lose(l[i], p[i], s[i]);
sp_lose[n][0] = dungeon_lose(n, 0, 0);
for(int t=1;t<=20;t++)
{
for(int i=0;i<=n;i++)
{
int next = sp_lose[i][t-1].n;
sp_lose[i][t] = f_lose(sp_lose[i][t-1], sp_lose[next][t-1]);
}
}
}
long long simulate(int x, int z) {
while(x != N)
{
for(int t=20;t>=0;t--)
{
if(sp_lose[x][t].x > z)
{
z += sp_lose[x][t].sum;
x = sp_lose[x][t].n;
}
}
for(int t=20;t>=0;t--)
{
if(sp[x][t].x <= z)
{
z += sp[x][t].sum;
x = sp[x][t].n;
}
}
}
return z;
}
