Jakarta Skyscrapers

Jakarta has $N$ tall buildings standing in a straight line. They are numbered $0, 1, \dots, N-1$ from the left. The city has no other tall buildings.

$M$ mysterious creatures called doges live in the city. The doges are numbered $0, 1, \dots, M-1$. Doge $i$ starts on building $B_i$, and the strength of its mysterious power is the positive integer $P_i$. A doge with power $p$ standing on building $b$ can move to building $b+p$ or building $b-p$ in one jump. The destination number must be at least $0$ and less than $N$.

Doge 0 leads all the doges. It has urgent news for doge 1 and wants the news delivered as fast as possible. A doge that has heard the news can do one of two things.

• Jump to another building with its own power.
• Pass the news to another doge standing on the same building.

Write a program that computes the smallest number of jumps needed to bring the news to doge 1. If there is no way to deliver it, detect that as well.

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

• $1 \le N \le 30000$
• $2 \le M \le 30000$
• $0 \le B_i < N$
• $1 \le P_i \le 30000$

Print the smallest number of jumps on the first line. Print $-1$ if the news cannot reach doge 1.

Consider a city with 5 buildings and 3 doges. Doge 0 is on building 0 with power 2, doge 1 is on building 1 with power 1, and doge 2 is on building 4 with power 1. The following order delivers the news in 5 jumps.

• Doge 0 jumps to building 2, then jumps to building 4. (2 jumps)
• Doge 0 passes the news to doge 2 on building 4.
• Doge 2 jumps to building 3, then building 2, then building 1. (3 jumps)
• Doge 2 passes the news to doge 1 on building 1.