| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1139 | 297 | 205 | 26.015% |
오름은 올라야만 한다.
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을 출력한다.
4 3 2 2 4 0 5 3
2
3 1 3 1
3
3 1 1 1
-1