#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=400000+10,lg=18,maxm=maxn*2;
long long sp[maxm][lg],wsp[maxm][lg],ezafsp[maxm][lg];
long long n,all[maxm],r[maxm],l[maxm],s[maxm],p[maxm],inf=1e15+5;
struct stbor{
long long tamam,ezaf,kam;
stbor(){
ezaf=0;
kam=inf;
}
}fakebor;
stbor boro(long long ind,long long now,long long len){
if(ind==n){
stbor ret;
ret.ezaf=now;
ret.kam=inf;
ret.tamam=ind;
return ret;
}
if(len==0){
stbor ret;
ret.ezaf=now;
ret.kam=inf;
ret.tamam=ind;
return ret;
}
long long ziad=now;
long long u=ind;
if(now>=s[ind]){
ziad-=s[ind];
}else{
u=ind+maxn;
}
stbor ret;
for(long long j=lg-1;j>=0;j--){
if((1<<j)<=len&&wsp[u][j]>ziad){
ret=boro(sp[u][j],ezafsp[u][j]+ziad,len-(1<<j));
ret.kam=min(ret.kam,wsp[u][j]-ziad);
return ret;
}
}
return ret;
}
void calsp(){
for(long long i=0;i<n;i++){
sp[i][0]=r[i];
wsp[i][0]=inf;
ezafsp[i][0]=s[i]+s[i];
sp[i+maxn][0]=l[i];
wsp[i+maxn][0]=inf;
wsp[i+maxn][0]=s[i];
ezafsp[i+maxn][0]=p[i];
}
sp[n][0]=n;
wsp[n][0]=inf;
ezafsp[n][0]=0;
for(long long lev=1;lev<lg;lev++){
for(long long i=0;i<=n;i++){
// cout<<i<<" "<<lev<<endl;
stbor tof=boro(sp[i][lev-1],ezafsp[i][lev-1],(1<<(lev-1)));
sp[i][lev]=tof.tamam;
wsp[i][lev]=min(wsp[i][lev-1],tof.kam);
ezafsp[i][lev]=tof.ezaf;
tof=boro(sp[i+maxn][lev-1],ezafsp[i+maxn][lev-1],(1<<(lev-1)));
sp[i+maxn][lev]=tof.tamam;
wsp[i+maxn][lev]=min(wsp[i+maxn][lev-1],tof.kam);
ezafsp[i+maxn][lev]=tof.ezaf;
}
}
}
void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
n=n_;
fakebor.tamam=n;
for(long long i=0;i<n;i++){
s[i]=s_[i];
l[i]=l_[i];
r[i]=w_[i];
p[i]=p_[i];
}
calsp();
return;
}
long long simulate(int x,int z) {
stbor ret=boro(x,z,1e9);
return ret.ezaf;
}
