시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 256 MB 14 1 (7%) 1
문제
시간 제한 1초, 메모리 제한 256MB 자카르타에는 $N$개의 일렬로 늘어선 마천루가 있다. 편의상 왼쪽부터 오른쪽으로 $0$번부터 $N-1$번으로 번호를 붙이자. 그리고 자카르타에는 이것들 말고 다른 마천루는 존재하지 않는다. 자카르타에는 "도지"라 불리는 $M$마리의 신비스런 생물이 살고있다. 도지들은 편의상 $0$번부터 $M-1$번까지 번호가 붙어있다. $i$번 도지는 $B_i$번 마천루에 살고있다. $i$번 도지는 신비한 힘을 가지고 있고 이를 양의 정수 $P_i$로 표현할 수 있다. 이 신비한 힘을 통해 도지는 마천루 사이를 뛰어다닐 수 있다. $p$만큼의 힘을 가지고 있는 도지가 $b$번 마천루에서 한 번 뛰면 $b+p$번 마천루($0 ≤ b+p < N$ 일때) 혹은 $b-p$번 마천루($0 ≤ b-p < N$ 일때)로 갈 수 있다. $0$번 도지가 가장 대단한 도지이며 모든 도지들의 지도자이다. 그리고 그는 $1$번 도지에게 전해야할 급한 소식이 있어서 그에게 빠르게 도달하고자 한다. 그 소식을 전달받은 도지는 아래와 같은 행동을 할 수 있다. - 다른 마천루로 뛰어서 넘어간다. - 같은 마천루에 있는 도지에게 소식을 전달한다. $1$번 도지에게 소식을 전달하기 위해서 모든 도지들이 뛰어야 할 횟수의 합의 최소값을 계산하거나 이것이 불가능한 일인지 계산하라.
입력
첫째 줄에 띄어쓰기로 구분된 두 개의 정수 $N, M$이 주어진다. 다음 $M$개의 줄에는 두 개의 정수 $B_i$와 $P_i$가 주어진다.
출력
한 줄에 총 뛰어야 할 횟수의 최소값을 출력하거나 불가능하다면 -1을 출력하라.
힌트
#### 예제 입력 ``` 5 3 0 2 1 1 4 1 ``` #### 예제 출력 ``` 5 ``` #### 설명 아래는 5번의 점프로 소식을 전달할 수 있는 방법 중 하나이다. - 0번 도지가 2번 마천루, 4번 마천루로 간다. (2번 뜀) - 0번 도지가 2번 도지에게 소식을 전달한다. - 2번 도지가 3번 마천루, 2번 마천루, 1번 마천루로 간다. (3번 뜀) - 2번 도지가 1번 도지에게 소식을 전달한다. #### 서브태스크 - 모든 서브태스크에 대해 - $0 ≤ B_i ≤ N$ - 서브태스크 1 (10점) - $1 ≤ N ≤ 10$ - $1 ≤ P_i ≤ 10$ - $2 ≤ M ≤ 3$ - 서브태스크 2 (12점) - $1 ≤ N ≤ 100$ - $1 ≤ P_i ≤ 100$ - $2 ≤ M ≤ 2,000$ - 서브태스크 3 (14점) - $1 ≤ N ≤ 2,000$ - $1 ≤ P_i ≤ 2,000$ - $2 ≤ M ≤ 2,000$ - 서브태스크 4 (21점) - $1 ≤ N ≤ 2,000$ - $1 ≤ P_i ≤ 2,000$ - $2 ≤ M ≤ 30,000$ - 서브태스크 5 (43점) - $1 ≤ N ≤ 30,000$ - $1 ≤ P_i ≤ 30,000$ - $2 ≤ M ≤ 30,000$