#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int inf = 0x3f3f3f3f,N = 4e5 + 5,B = 16,L = 7;
//The key observation is that every time we win our damage doubles
struct info{
//next place and the attack you need to win a game
int nxt,atk;
//overall attack we gained
ll sum;
info operator + (const info a)const{
int res;
if(a.atk == inf)res = atk;
else res = max(0ll,min((ll)atk,a.atk - sum));
return (info){a.nxt,res,sum + a.sum};
}
}f[L][25][N];
int n,powB[L];
vi s,p,w,l;
ll simulate(int x,int z_){
ll z = z_;
int i = 0;
while(114514){
while(i + 1 < L && z > powB[i+1]) i++;
for(int j = 24;j >= 0;j--){
info now = f[i][j][x];
if(now.nxt == n)continue;//jumping too far
if(now.atk != inf && now.atk <= z)continue;
z += now.sum, x = now.nxt;
}
if(z >= s[x]) z += s[x], x = w[x];
else z += p[x], x = l[x];
if(x == n)return z;
}
}
void prework(int X,int k){
for(int i = 0;i < n;i++){
if(X >= s[i]){
f[k][0][i] = (info){w[i],inf,s[i]};
}else f[k][0][i] = (info){l[i],s[i],p[i]};
}
for(int j = 1;j < 25;j++)for(int i = 0;i < n;i++){
info t = f[k][j-1][i];
f[k][j][i] = t + f[k][j-1][t.nxt];
}
}
void init(int _n,vi _s,vi _p,vi _w,vi _l){
n = _n,s = _s,p = _p,w = _w,l = _l;
w.pb(n),l.pb(n);
powB[0] = 1;
prework(1,0);
for(int d = 1;d < L;d++){
powB[d] = powB[d-1] * B;
prework(powB[d],d);
}
}
