#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
const int MX = 25;
int pos[MX][400001][8], mx[MX][400001][8], sum[MX][400001][8];
int tmp1[400001], tmp3[400001], tmp2[400001];
ll dp[400001];
void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
N = n;
for(int j = 0; j < MX; ++j) {
for(int i = 0; i < N; ++i) {
pos[j][i][0] = (1 << j) <= S[i] ? L[i] : W[i];
sum[j][i][0] = (1 << j) <= S[i] ? P[i] : S[i];
mx[j][i][0] = (1 << j) <= S[i] ? -S[i] : -(1 << 29);
}
pos[j][N][0] = N, sum[j][N][0] = 0;
}
for(int k = 0; k < MX; ++k) for(int j = 1; j <= 7; ++j) {
for(int i = 0; i <= N; ++i) {
pos[k][i][j] = pos[k][pos[k][i][j - 1]][j - 1];
sum[k][i][j] = sum[k][pos[k][i][j - 1]][j - 1] + sum[k][i][j - 1];
mx[k][i][j] = max(mx[k][i][j - 1], sum[k][i][j - 1] + mx[k][pos[k][i][j - 1]][j - 1]);
sum[k][i][j] = min(1 << 29, sum[k][i][j]);
mx[k][i][j] = min(0, mx[k][i][j]);
tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j];
}
for(int i = 0; i <= N; ++i) {
mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]);
sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i];
pos[k][i][j] = tmp1[tmp1[i]];
sum[k][i][j] = min(1 << 29, sum[k][i][j]);
mx[k][i][j] = min(0, mx[k][i][j]);
}
for(int i = 0; i <= N; ++i) tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j];
for(int i = 0; i <= N; ++i) {
mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]);
sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i];
pos[k][i][j] = tmp1[tmp1[i]];
sum[k][i][j] = min(1 << 29, sum[k][i][j]);
mx[k][i][j] = min(0, mx[k][i][j]);
}
for(int i = 0; i <= N; ++i) tmp1[i] = pos[k][i][j], tmp2[i] = sum[k][i][j], tmp3[i] = mx[k][i][j];
for(int i = 0; i <= N; ++i) {
mx[k][i][j] = max(tmp3[i], tmp2[i] + tmp3[tmp1[i]]);
sum[k][i][j] = tmp2[tmp1[i]] + tmp2[i];
pos[k][i][j] = tmp1[tmp1[i]];
sum[k][i][j] = min(1 << 29, sum[k][i][j]);
mx[k][i][j] = min(0, mx[k][i][j]);
}
}
for(int i = 0; i <= N; ++i) {
int x = i;
for(int j = 7; j >= 0; --j) {
for(int t = 0; t < 15; ++t) {
if(pos[MX - 1][x][j] != N) dp[i] += sum[MX - 1][x][j], x = pos[MX - 1][x][j];
else break;
}
}
dp[x] += sum[MX - 1][x][0];
}
return;
}
long long simulate(int x, int z) {
ll ans = z;
for(int k = 0; k < MX - 1; ++k) {
for(int j = min(7, k); j >= 0; --j) for(int t = 0; t < 15; ++t) {
if(!(pos[k][x][j] == N || mx[k][x][j] + ans >= 0ll)) ans += sum[k][x][j], x = pos[k][x][j];
else break;
}
if(ans < (1 << k)) ans += sum[k][x][0], x = pos[k][x][0];
if(x == N) return ans;
}
return dp[x];
}
