34854번 - $N$중 슬릿 실험 스페셜 저지

문제

당신은 가로 길이가 2ドルM$이고 세로 길이가 $N+1$인 직사각형에서 $N$중 슬릿 실험을 하려 한다. 직사각형의 맨 왼쪽 아래는 $(-M, 0)$이며 맨 오른쪽 위는 $(M, N+1)$이다.

$N$중 슬릿 실험은 직사각형 내부에 $N$개의 슬릿을 놓고 시행한다. $i$번째 슬릿은 $(-M, i)$부터 $(M, i)$까지를 잇는 선분 형태의 벽이며 $(a_{i}, i)$부터 $(b_{i}, i)$까지 구멍이 뚫려 있다.

피실험체는 초당 1ドル$의 속력으로 $(0, 0)$에서 출발해 직사각형의 내부를 통해 $(0, N+1)$까지 최단 경로로 이동한다. 피실험체가 $(0, 0)$에서 출발해 $(0, N+1)$까지 이동하는 데 몇 초가 걸리는지 구하여라.

피실험체는 출발지와 도착지를 제외하고는 직사각형의 어떤 변도 지날 수 없으며 벽이 있는 곳 역시 지날 수 없다. 벽의 두께와 피실험체의 크기 등은 무시한다.

입력

첫째 줄에 $M$과 $N$이 공백으로 구분되어 주어진다. (1ドル \le M \le 10^{6};$ 1ドル \le N \le 100$)

이후 $N$개 줄에 걸쳐 그중 $i$번째 줄에는 $a_{i}$와 $b_{i}$가 공백으로 구분되어 주어진다. ($-M \le a_{i} \lt b_{i} \le M$)

입력으로 주어지는 모든 수는 정수이다.

출력

피실험체가 $(0, 0)$에서 출발해 $(0, N+1)$까지 이동하는 데 몇 초가 걸리는지 출력한다. 절대/상대 오차는 10ドル^{-6}$까지 허용한다.

제한

노트