P3645 [APIO2015] Jakarta Skyscrapers

There are $N$ skyscrapers in Jakarta, the capital of Indonesia, arranged in a straight line and numbered from $0$ to $N - 1$ from left to right. There are no other skyscrapers in Jakarta besides these $N$. There are $M$ mysterious creatures called "doge" living in Jakarta, numbered from $0$ to $M - 1$. Doge $i$ initially lives at skyscraper $B_i$. Each doge has a mysterious power that allows it to jump between skyscrapers. The jumping ability of doge $i$ is $P_i$ ($P_i > 0$). In one jump, a doge at skyscraper $b$ with jump ability $p$ can jump to skyscraper $b - p$ (if $0 \leq b - p < N$) or to skyscraper $b + p$ (if $0 \leq b + p < N$). Doge $0$ is the leader of all doges, and it needs to deliver an urgent message to doge $1$ as soon as possible. Any doge that has received the message has two options: - Jump to another skyscraper. - Pass the message to another doge currently on the same skyscraper. Please help the doges compute the minimum total number of jumps required to deliver the message from doge $0$ to doge $1$, or determine that the message can never reach doge $1$.

The first line contains two integers $N$ and $M$. Each of the next $M$ lines contains two integers $B_i$ and $P_i$.

Output one line with the minimum number of steps required. If the message can never reach doge $1$, output $-1$.

Sample explanation: Below is a solution with a total of $5$ jumps: - Doge $0$ jumps to skyscraper $2$, then jumps to skyscraper $4$ ($2$ jumps). - Doge $0$ passes the message to doge $2$. - Doge $2$ jumps to skyscraper $3$, then jumps to skyscraper $2$, and then jumps to skyscraper $1$ ($3$ jumps). - Doge $2$ passes the message to doge $1$. Constraints: All testdata guarantee $0 \leq B_i < N$. Subtask 1 (10 points) - $1 \leq N \leq 10$ - $1 \leq P_i \leq 10$ - $2 \leq M \leq 3$ Subtask 2 (12 points) - $1 \leq N \leq 100$ - $1 \leq P_i \leq 100$ - $2 \leq M \leq 2000$ Subtask 3 (14 points) - $1 \leq N \leq 2000$ - $1 \leq P_i \leq 2000$ - $2 \leq M \leq 2000$ Subtask 4 (21 points) - $1 \leq N \leq 2000$ - $1 \leq P_i \leq 2000$ - $2 \leq M \leq 30000$ Subtask 5 (43 points) - $1 \leq N \leq 30000$ - $1 \leq P_i \leq 30000$ - $2 \leq M \leq 30000$ Translated by ChatGPT 5