T517979 Strange Dino Game (English ver.)

[Chinese statement](https://www.luogu.com.cn/problem/T466381). **You must submit your code at the Chinese version of the statement.**   Watersphere is at home, with Internet disconnected. He has nothing to do, but playing the game Dino. However, he is poor at Dino, getting dizzy after playing for a while. So, he let you help him to get a better score. This problem is based on the game [Dino](https://dinosaur.game). You may click the link to have a try, to have a better understanding.

We describe this problem on a 2D plane. First, we list out some elements of the game. - Player: Dino. We treat Dino as a point. - Obstacle: - Cactus: A segment, whose endpoints are $(x_i',0)$ and $(x_i',h_i)$. - Bird: A segment, whose endpoints are $(x_i,d_i)$ and $(x_i,u_i)$. - Game Over: The game ends, once the position of Dino coincides with any obstacle, including the both ends of the segments. - Starting point: $(0,0)$ (origin). - Endpoint: The position of Dino when the game ends. It is possible that the game has no endpoint, i.e. Dino can go forever. - Score: The $x$-coordination of the endpoint. When there is no endpoint, the score is defined to be infinity. - Jumping arguments: Positive integers $d,h$. - Walking: Dino moves towards the positive direction of the $x$-axis **when Dino is on the $x$-axis**. - Jumping: **When Dino is on the $x$-axis**, Dino can perform a jump. Take the point where Dino starts jumping as origin, the trajectory of jumping can be described as the following function: $$f(x) = \begin{cases} \displaystyle \frac{h}{d}x & x\in [0, d) \\ \displaystyle-\frac{h}{d}x+2h & x\in [d, 2d) \\ \end{cases}$$ - Note that, we can infer that, **it is possible to make the second jump immediately right after the first jump ends.** - Note that, it is possible to make a jump at an **arbitrary point with a real coordination** (as long as it is on the $x$-axis), not necessarily at an integer point. The figure below shows a jump where $d=2,h=6$.  In a round of game, starting from the origin, Dino moves towards the positive direction of $x$-axis. The goal is to maximize the score, that is, to bypass the obstacles, making himself move as far as possible. At every instant, Dino can only do one thing: Walk, or jump. Dino can make a jump if and only if he is on the $x$-axis. Formally, the behavior of Dino can be described as a sequence of length $(k+1)$ consisting of tuples of real numbers $[(x_0,t_0),(x_1,t_1),\cdots,(x_k,t_k)]$, where the following conditions holds: - $x_0=0$; - $t_i\in \{0,1\}$; - $\forall 0\le i\lt k$, $x_i\lt x_{i+1}$; - $t_i=1,i\lt k\implies x_{i+1}-x_i\ge 2d$; (You cannot make the second jump before the first jump ends) - $\forall 0\le i\lt k$, $t_i=t_{i+1}\implies t_i=t_{i+1}=1$. When $t_i=0$, we say Dino **starts walking** at $x_i$; Otherwise, when $t_i=1$, we say Dino **starts jumping** at $x_i$. The game ends when the position of Dino coinsides with any obstacle. Let's say the position of Dino, at this moment, is the endpoint; and the score is the $x$-coordination of the endpoint. There are $b$ birds and $c$ cacti. You are to calculate the maximum possible score that Dino can obtain. Specially, the score can be infinity. For better understanding, see the figure in the sample description.

无

无

Explanation of sample $1$: - For the first round, Dino can't bypass the second cactus, thus the answer is the $x$ coordination of the second cactus. - For the second round, for example, Dino can bypass the only obstacle by starting jumping at origin. A possible move of the first round is shown below, in which red segments denote the birds, green segments denote the cacti and pink segments denote Dino.  ### Contraints - Subtask 1 (5 pts): $c=0$; - Subtask 2 (5 pts): $b,c \le 10$; - Subtask 3 (20 pts): $b=0$; - Subtask 4 (20 pts): $1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i \le 10^5$; - Subtask 5 (40 pts): No further contraints. - Subtask 6 (10 pts): No further contraints. It is guaranteed that - $1 \le T \le 10$; - $0 \le b,c \le 2\times 10^4$; - $1 \le d,h,x_{b_i},d_i,u_i,x_i',h_i\le 10^9$; - $d_i\le u_i$.