특별한 오름 등반

오름은 올라야만 한다.

NLCS Jeju의 기숙사 이름 "오름"은 제주에서 봉우리나 산을 부르는 말인 오름에서 따왔다. 각 기숙사의 학생들은 1년에 한 번, 기숙사 이름의 기원이 된 오름을 직접 오른다.

오름은 $xy$ 평면에서 세 점 $(0, 0)$, $(N, N)$, $(2N, 0)$을 잇는 삼각형 모양이다. 당신은 $(0, 0)$에서 출발해 $(2N, 0)$에 도착해야 한다.

$(x, y)$에서는 $(x+1, y+1)$ 또는 $(x+1, y-1)$로만 이동할 수 있다. 이동하여 도착한 위치는 오름의 내부 또는 경계여야 한다.

오름에서는 길을 잃기 쉬워서, 길을 잃기 쉬운 $M$개의 지점에 선생님들이 계신다. 그런데 숙제를 하지 않은 당신은 선생님을 만나는 것이 부담스러우니, 선생님을 피해서 이동해야 한다.

또한 오름 등산을 특별한 기억으로 남기려고 사진을 찍기로 했다. 사진의 아름다움은 사진을 찍은 높이가 높을수록 커진다. 정확히는 사진을 찍은 위치의 $y$좌표가 그 사진의 아름다움 수치가 된다.

찍을 수 있는 사진의 아름다움 수치의 최댓값을 구하시오.

첫째 줄에 오름의 높이 $N$과 선생님이 계신 지점의 개수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M+1$번째 줄까지 선생님의 $x$좌표 $x\_i$와 $y$좌표 $y\_i$가 공백으로 구분되어 주어진다. 선생님은 항상 오름의 내부 또는 경계에 있다.

첫째 줄에 찍을 수 있는 사진의 아름다움 수치의 최댓값을 출력한다. 단, 시작 지점에서 도착 지점까지 이동할 수 없으면 -1을 출력한다.

• $1 \le N \le 1\,000$
• $0 \le M \le \min\left(\frac{(N+1)(N+2)}{2} - 1, 100\,000 \right)$
• $0 \le x\_i \le 2N$
• $0 \le y\_i \le N$
• $x\_i + y\_i$는 짝수다.
• $(0,0)$에는 선생님이 계시지 않는다.