#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline void mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline void mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#ifdef DEBUG
#define debug(args...) _debug(args)
inline void _debug(const char* format, ...) {
va_list args;
va_start(args, format);
vprintf(format, args);
va_end(args);
}
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 100005
#define MAXL 30
int n;
vi s, p, w, l, v;
set<int> st;
int nxt[10][MAXL][MAXN];
ll d[10][MAXL][MAXN];
void init(int _n, vi _s, vi _p, vi _w, vi _l) {
n = _n; s = _s, p = _p, w = _w, l = _l;
s.pb(0);
p.pb(0);
w.pb(n);
l.pb(n);
REP (i, 0, n) {
st.insert(s[i]);
}
v.pb(0);
for (auto &i : st) {
v.pb(i);
}
REP (it, 0, v.size()) {
debug("%d:\n", v[it]);
REP (i, 0, n + 1) {
if (s[i] <= v[it]) {
nxt[it][0][i] = w[i];
d[it][0][i] = s[i];
debug(" %d -> %d %d\n", i, w[i], s[i]);
} else {
nxt[it][0][i] = l[i];
d[it][0][i] = p[i];
debug(" %d -> %d %d\n", i, l[i], p[i]);
}
}
REP (k, 1, MAXL) {
REP (i, 0, n + 1) {
nxt[it][k][i] = nxt[it][k - 1][nxt[it][k - 1][i]];
d[it][k][i] = d[it][k - 1][i] + d[it][k - 1][nxt[it][k - 1][i]];
}
}
}
return;
}
ll simulate(int x, int z) {
ll ans = z;
REP (i, 0, v.size()) {
ll mx = LINF;
if (i + 1 != v.size()) mx = v[i + 1]; // < mx
if (ans >= mx) continue;
debug("%d\n", v[i]);
RREP (k, MAXL - 1, 0) {
if (ans + d[i][k][x] < mx) {
ans += d[i][k][x];
x = nxt[i][k][x];
debug(" %d: %lld\n", x, ans);
}
}
ans += d[i][0][x];
x = nxt[i][0][x];
debug(" %d: %lld\n", x, ans);
}
return ans;
}
