#include "dungeons.h"
#include <vector>
#include<iomanip>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pi pair<ll, ll>
#define vp vector<pi>
#define vvp vector<vp>
ll oo = (ll)1 << 60;
struct node {
ll max = -1; // max or min
ll min = -1;
ll to = -1;
ll gain = -1;
void print() {
cerr << "node : {max : " << max << ", min : " << min << ", to : " << to << ", gain : " << gain << "}\n";
}
};
int n;
vi S, P, W, L;
vector<map<ll, node>> B1, B;
void print(vi &L1) {
cerr << "{";
for (auto i : L1) {
cerr << i << ", ";
}
cerr << "}\n";
}
void print(vl &L1) {
cerr << "{";
for (auto i : L1) {
cerr << i << ", ";
}
cerr << "}\n";
}
void print(vector<vector<node>> &L1) {
cerr << "{\n";
for (auto i : L1) {
cerr << "{\n";
for (auto j : i) {
j.print();
}
cerr << "},\n";
}
cerr << "}\n";
}
void print(vector<map<ll, node>> &L1) {
cerr << "{\n";
for (auto i : L1) {
cerr << "{\n";
for (auto j : i) {
cerr << j.first << " : ";
j.second.print();
}
cerr << "},\n";
}
cerr << "}\n";
}
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
n = N;
S = s;
P = p;
W = w;
L = l;
B1 = vector<map<ll, node>>(n);
B = vector<map<ll, node>>(n);
//cerr << "oo : " << oo << endl;
for (int i = 0; i < n; i++) {
B1[i] = {{0, {S[i], 0, L[i], P[i]}}, {S[i], {oo, S[i], W[i], S[i]}}};
}
//cerr << "B1 : ";
//print(B1);
for (int i = 0; i < log2(1e7)+2; i++) {
for (int j = 0; j < n; j++) {
B[j] = {};
for (auto i : B1[j]) {
node a = i.second;
if (a.to == n) {
B[j][a.min] = a;
continue;
}
for (auto i : B1[a.to]) {
node b = i.second;
if (a.min + a.gain >= b.max) continue;
if (a.max + a.gain <= b.min) continue;
node c = {min(oo, min(a.max, b.max - a.gain)), max((ll)0, max(a.min, b.min - a.gain)), b.to, a.gain + b.gain};
if (B[j].find(c.min) != B[j].end()) {
//cerr << "ERROR B[" << j << "][" << c.min << "] already exist\n";
//cerr << "B[" << j << "][" << c.min << "] : ";
//B[j][c.min].print();
//cerr << "c : ";
//c.print();
}
B[j][c.min] = c;
}
}
}
B1 = B;
}
/*
print(B);
//*/
return;
}
ll oink(ll x, ll z) {
auto a = B[x].upper_bound(z);
a--;
return (z + (*a).second.gain);
}
long long simulate(int x, int z) {
return oink(x, z);
}
