#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAXS 40 //MAX sparse table
#define MAXI 25 //MAX interval
#define MAXSI 351
#define INF 10101010
#define MAX 404040
#define B 1
#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))
vector<pair<int, int>> win, lose; //next
int nxt[MAX][MAXSI], limit[MAX][MAXSI], delta[MAX][MAXSI];
ll dp[MAX];
int f[30][30];
int N;
ll get(int x) {
if (x == N) return 0;
if (dp[x]) return dp[x];
return dp[x] = get(win[x].first) + win[x].second;
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
int i, j;
for (i = 0; i <= 25; i++) {
for (j = 0; j <= i; j++) f[i][j] = j + (i * (i + 1) / 2);
}
win.resize(N + 1);
lose.resize(N + 1);
for (i = 0; i < N; i++) {
win[i] = { w[i], s[i] };
lose[i] = { l[i], p[i] };
}
int k;
for (k = 0; k < MAXI; k++) {
int low, high;
low = 1 << k;
high = 1 << (k + 1);
for (i = 0; i < N; i++) {
if (s[i] < low) {
nxt[i][f[k][0]] = win[i].first;
delta[i][f[k][0]] = win[i].second;
limit[i][f[k][0]] = INF;
}
else if (s[i] >= high) {
nxt[i][f[k][0]] = lose[i].first;
delta[i][f[k][0]] = lose[i].second;
limit[i][f[k][0]] = s[i];
}
else {
nxt[i][f[k][0]] = lose[i].first;
delta[i][f[k][0]] = lose[i].second;
limit[i][f[k][0]] = s[i];
}
}
nxt[N][f[k][0]] = N;
delta[N][f[k][0]] = 0;
limit[N][f[k][0]] = INF;
int j;
for (j = 1; j <= k; ++j) {
for (i = 0; i <= N; ++i) {
int v = nxt[i][f[k][j - 1]];
nxt[i][f[k][j]] = nxt[v][f[k][j - 1]];
delta[i][f[k][j]] = min(50000000, delta[i][f[k][j - 1]] + delta[v][f[k][j - 1]]);
limit[i][f[k][j]] = max(0, min(limit[v][f[k][j - 1]] - delta[i][f[k][j - 1]], limit[i][f[k][j - 1]]));
}
}
}
for (i = 0; i < N; i++) get(i);
return;
}
long long simulate(int x, int Z) {
ll z = Z;
ll i;
for (i = 0; i < MAXI; i++) {
ll high;
high = 1 << (i + 1);
if (i == MAXI - 1) break;
if (high <= z) continue;
int k;
bool c = 0;
for (k = i; k >= 0; k--) {
while (limit[x][f[i][k]] > z) {
if (delta[x][f[i][k]] > 20000000) {
c = 1;
break;
}
z += delta[x][f[i][k]];
x = nxt[x][f[i][k]];
if (high <= z) break;
if (x == N) return z;
}
if (c) break;
if (high <= z) break;
if (x == N) return z;
}
if (x == N) return z;
if (c) {
for (; k >= 0; k--) {
if (limit[x][f[i][k]] > z) {
while (delta[x][f[i][k]] <= 20000000) {
z += delta[x][f[i][k]];
x = nxt[x][f[i][k]];
if (z > 1000000) return z + dp[x];
if (high <= z) break;
if (x == N) return z;
}
if (high <= z) break;
if (x == N) return z;
}
}
if (z > 1000000) return z + dp[x];
continue;
}
if (high <= z) continue;
if (z >= win[x].second) z += win[x].second, x = win[x].first;
else z += lose[x].second, x = lose[x].first;
if (x == N) break;
}
return z + dp[x];
}
