package main
import (
"bufio"
"container/list"
"fmt"
"math"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
// 입력
var N, M int
fmt.Fscan(reader, &N, &M)
B := make([]int, M)
P := make([]int, M)
for i := 0; i < M; i++ {
fmt.Fscan(reader, &B[i], &P[i])
}
// dogesAt[b] = 이 빌딩에 "원래" 위치한 도지들의 리스트
dogesAt := make([][]int, N)
for i := 0; i < N; i++ {
dogesAt[i] = []int{}
}
for i := 0; i < M; i++ {
b := B[i]
dogesAt[b] = append(dogesAt[b], i)
}
// dist[b][i] : 도지 i가 빌딩 b에서 뉴스를 가지고 있는 상태가 되기까지의 최소 점프 수
// 초기값: 매우 큰 수
const INF = math.MaxInt32
dist := make([][]int, N)
for b := 0; b < N; b++ {
dist[b] = make([]int, M)
for i := 0; i < M; i++ {
dist[b][i] = INF
}
}
// 시작 상태: (B[0], 0) (도지 0이 빌딩 B[0], dist=0)
dist[B[0]][0] = 0
// 0-1 BFS용 deque
dq := list.New()
dq.PushBack([2]int{B[0], 0}) // (b, i)
for dq.Len() > 0 {
front := dq.Front()
dq.Remove(front)
b, i := front.Value.[2]int{b, i} // 해석 오류: Go에서는 destructuring이 지원 안 됨. 아래에서 수정.
// Go에서 front.Value는 interface{}이므로, 실제 배열로 캐스팅
curState := front.Value.([2]int)
b, i = curState[0], curState[1]
d := dist[b][i]
if i == 1 {
// 도지 1이 뉴스를 획득 -> 답
fmt.Fprintln(writer, d)
return
}
// 1) 같은 빌딩 b에 있는 "원래 위치가 b"인 도지 j 에게 뉴스를 전달(비용 0)
for _, j := range dogesAt[b] {
if dist[b][j] > d {
dist[b][j] = d
dq.PushFront([2]int{b, j})
}
}
// 2) 점프(비용 1)
// doge i (이미 뉴스 보유)가 점프
// b + P[i], b - P[i] 범위 체크
newB1 := b + P[i]
if newB1 >= 0 && newB1 < N {
nd := d + 1
if dist[newB1][i] > nd {
dist[newB1][i] = nd
dq.PushBack([2]int{newB1, i})
}
}
newB2 := b - P[i]
if newB2 >= 0 && newB2 < N {
nd := d + 1
if dist[newB2][i] > nd {
dist[newB2][i] = nd
dq.PushBack([2]int{newB2, i})
}
}
}
// BFS가 끝났는데도 도지1에게 전달 불가
fmt.Fprintln(writer, -1)
}
