시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 142 17 15 35.714%

문제

자카르타 시에는 N개의 큰 빌딩이 일직선 위에 위치하고 있다. 이들은 왼쪽부터 0, 1, ..., N - 1까지 번호가 붙어 있다. 자카르타에는 이들 말고 다른 큰빌딩은 없다.

자카르타에는 "도게"라고 불리는 신비한 생명체들이 살고 있다. 도게들은 0, 1, ..., M - 1 까지 번호가 붙어 있다. 도게 i는 최초에 빌딩 Bi에 위치하고 있다. 도게 i가 가진 신비한 힘은 그 능력치가 양의 정수 Pi로 표시된다. 도게는 이 신비한 힘으로 큰 빌딩들 간에 점프를 할 수 있다. 큰 빌딩 b에 있는 능력치가 p인 도게는 한번의 점프로 큰빌딩 b + p(0 ≤ b + p < N이라야 함) 혹은 큰빌딩 b - p(0 ≤ b - p < N이라야 함)로 이동할 수 있다.

도게 0이 가장 대단한 도게이며 모든 도게들의 지도자이다. 도게 0은 급한 소식이 있어 이 소식을 도게 1에게 전해야 한다. 물론 가장 빨리 소식이 전해지기를 바란다. 뉴스를 전해 들은 도게는 다음의 두가지 중 하나를 할 수 있다.

  • 다른 큰 빌딩으로 점프.
  • 현재 위치한 빌딩의 다른 도게에게 소식을 전달

도게들을 도와주는 프로그램을 작성해야 한다. 이 프로그램은 소식을 도게 1에게 전할 수 있는 최소한의 점프 횟수를 계산해야 한다. 만약 소식을 전달하는 것이 불가능한 경우라면 그것도 알아내야 한다.

입력

입력의 첫 줄에는 정수 NM이 주어진다. 이후 M개의 줄에는 두 자연수 BiPi가 주어진다.

  • 0 ≤ Bi < N
  • 1 ≤ N ≤ 30, 000
  • 1 ≤ Pi ≤ 30, 000
  • 2 ≤ M ≤ 30, 000

출력

출력은 단 한 줄이며, 최소의 점프 횟수라야 한다. 불가능한 경우 -1을 출력한다.

예제 입력

5 3
0 2
1 1
4 1

예제 출력

5

힌트

다음 경우가 5 번의 점프로 가능한 시나리오이다.

  • 도게 0이 큰빌딩 2로 점프, 또 큰빌딩 4로 점프 (2번 점프).
  • 도게 0이 소식을 도게 2에게 전함.
  • 도게 2가 큰빌딩 3으로 점프, 또 큰빌딩 2로 점프, 또 큰빌딩 1로 점프 (3번 점프).
  • 도게 2가 도게 1에게 소식을 전함.