자카르타의 마천루

자카르타에는 큰 빌딩 $N$개가 일직선 위에 서 있다. 왼쪽부터 $0, 1, \dots, N-1$번이다. 이 도시에 다른 큰 빌딩은 없다.

이 도시에는 도게라고 부르는 신비한 생명체 $M$마리가 산다. 도게에는 $0, 1, \dots, M-1$번이 붙어 있다. 도게 $i$는 처음에 빌딩 $B_i$에 있고, 신비한 힘의 능력치는 양의 정수 $P_i$다. 능력치가 $p$인 도게가 빌딩 $b$에 있으면 한 번의 점프로 빌딩 $b+p$나 빌딩 $b-p$로 옮겨 갈 수 있다. 단, 도착하는 빌딩 번호가 $0$ 이상 $N$ 미만이어야 한다.

도게 0은 모든 도게의 지도자다. 급한 소식이 생겨 이 소식을 도게 1에게 최대한 빨리 전하려고 한다. 소식을 들은 도게는 다음 두 가지 중 하나를 할 수 있다.

• 자신의 힘으로 다른 빌딩으로 점프한다.
• 지금 있는 빌딩에 함께 있는 다른 도게에게 소식을 전한다.

소식을 도게 1에게 전하는 데 필요한 최소 점프 횟수를 구하는 프로그램을 작성하시오. 전할 방법이 없으면 그 사실도 알아내야 한다.

첫째 줄에 정수 $N$과 $M$이 주어진다. 다음 $M$개 줄에는 $i$번째 줄마다 두 정수 $B_i$와 $P_i$가 주어진다.

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

첫째 줄에 최소 점프 횟수를 출력한다. 소식을 전할 수 없으면 $-1$을 출력한다.

빌딩이 5개이고 도게가 3마리인 경우를 보자. 도게 0은 빌딩 0에 있고 능력치가 2, 도게 1은 빌딩 1에 있고 능력치가 1, 도게 2는 빌딩 4에 있고 능력치가 1이다. 다음 순서를 따르면 점프 5번으로 소식을 전할 수 있다.

• 도게 0이 빌딩 2로 점프하고, 다시 빌딩 4로 점프한다. (점프 2번)
• 도게 0이 빌딩 4에 있는 도게 2에게 소식을 전한다.
• 도게 2가 빌딩 3, 빌딩 2, 빌딩 1로 차례로 점프한다. (점프 3번)
• 도게 2가 빌딩 1에 있는 도게 1에게 소식을 전한다.