Description

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$.

Input Format

The first line contains two integers $N$ and $M$.

Each of the next $M$ lines contains two integers $B_i$ and $P_i$.

Output Format

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

5 3
0 2
1 1
4 1

5

Hint

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