#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
private:
struct dAtA{
int to;
long long inc,thres;
dAtA(int go,int add,long long T){
to=go,inc=add,thres=T;
}
dAtA(){
to=0,inc=0,thres=0;
}
dAtA(dAtA a,dAtA b){
to=b.to;
inc=a.inc+b.inc;
thres=min(1ll*a.thres,b.thres-a.inc);
}
} bj[400100][24];
public:
long long strength(int n,int k){
return bj[n][k].inc;
}
long long thres(int n,int k){
return bj[n][k].thres;
}
int dungeon(int n,int k){
return bj[n][k].to;
}
void setdungeon(int n,int go,int add,long long T){
bj[n][0]=dAtA(go,add,T);
}
void preproc(int n){
for(int j=1;j<24;j++) for(int i=0;i<=n;i++)
bj[i][j]=dAtA(bj[i][j-1],bj[bj[i][j-1].to][j-1]);
}
} susss[9];
int l[400100],p[400100],s[400100],w[400100],fin;
long long pws[24];
int llog(int x){
for(int i=0;i<24;i++)
if(pws[i+1]>x)
return i;
}
void init(int n,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
fin=n;
pws[0]=1;
for(int i=1;i<24;i++)
pws[i]=pws[i-1]*10;
for(int i=0;i<n;i++) l[i]=L[i],p[i]=P[i],s[i]=S[i],w[i]=W[i];
for(int j=0;j<9;j++)
for(int i=0;i<n;i++) {
if(s[i]<=pws[j])
susss[j].setdungeon(i,w[i],s[i],1e18);
else susss[j].setdungeon(i,l[i],p[i],s[i]);
}
for(int i=0;i<9;i++)
susss[i].setdungeon(n,n,0,1e18),
susss[i].preproc(n);
}
long long simulate(int x, int Z) {
long long z=Z;
while(1){
int K=min(8,llog(z));
for(int i=24;i--;)
if(susss[K].thres(x,i)>z)
z+=susss[K].strength(x,i),
x=susss[K].dungeon(x,i);
if(x==fin) return z;
int k=s[x];
if(k<=z)
x=w[x],z+=k;
else x=l[x],z+=p[x];
if(x==fin) return z;
}
}
