P15743 [JAG 2024 Summer Camp #3] Tower Defense

There are $M + 1$ cells labeled from $0$ to $M$ arranged in sequence. Cell $0$ contains a base, and cell $M$ contains a monster with health $H$. There are $N$ soldiers deployed near the cells. The attack range of soldier $i$ is from cell $L_i$ to $R_i$ (i.e., cells $L_i, L_i + 1, \ldots, R_i$). Each turn, both the monster and the soldiers perform the following actions in order (first the monster, then the soldiers): - Monster: If the monster's health is $1$ or more and it is not in cell $0$, it moves one cell closer to the base (i.e., it moves to the cell with a number $1$ smaller). - Soldiers: Any soldier whose attack range includes the cell where the monster is currently located attacks the monster and reduces its health by $1$. If the monster's health drops to $0$ or below before it reaches cell $0$, the monster dies in that cell, the defense is successful, and the game ends. If the monster reaches cell $0$ without its health dropping to $0$ or below, the defense fails and the game ends. Determine whether the defense will succeed, and if so, find the number of the cell where the monster will die.

The input consists of a single test case of the following format. $$ \begin{aligned} &N \ M \ H \\ &L_1 \ R_1 \\ &\vdots \\ &L_N \ R_N \end{aligned} $$ The first line contains three integers, $N$, $M$, and $H$, representing the number of soldiers, the number of cells, and the monster's health, respectively. $N$ is between $1$ and $100,000$ (both inclusive). $M$ is between $2$ and $10^6$ (both inclusive). $H$ is between $1$ and $10^{11}$ (both inclusive). The next $N$ lines each contain two integers, $L_i$ and $R_i$, which represent the attack range interval of the $i$-th soldier. Both $L_i$ and $R_i$ are between $1$ and $M - 1$ (both inclusive). It is guaranteed that $L_i$ is less than or equal to $R_i$.

Output a single integer, the number of the cell where the monster will die if the defense is successful; otherwise, output $-1$.