개구리 징검다리

피오나는 개구리가 강을 건너는 게임 Froggy Ford를 만들고 있다. 강은 직선인 두 기슭 $x = 0$과 $x = w$ 사이를 흐르고, 물속에는 두 기슭 사이에 돌 $n$개가 놓여 있다.

개구리는 왼쪽 기슭의 아무 점에서나 출발해 돌을 차례로 밟고 오른쪽 기슭의 아무 점에나 도착한다. 기슭에서는 어느 점에서든 뛰고 어느 점에든 내려앉으므로, 점 $(x, y)$에 있는 돌과 왼쪽 기슭 사이의 도약 길이는 $x$, 오른쪽 기슭 사이의 도약 길이는 $w - x$이다. 한 기슭에서 맞은편 기슭으로 곧장 뛰는 도약의 길이는 $w$이고, 돌과 돌 사이의 도약 길이는 두 점의 유클리드 거리이다. 경로는 돌을 원하는 만큼 원하는 순서로 밟고, 경로의 비용은 그 경로에서 가장 긴 도약 하나의 길이이다.

개구리는 힘이 약해서 플레이어는 가장 긴 도약이 가장 짧아지는 경로를 고른다. 피오나는 개구리가 출발하기 전에 플레이어가 돌 하나를 강에 더 놓게 하려고 한다. 새 돌은 $0 < x^+ < w$, $-10^9 \le y^+ \le 10^9$을 만족하는 실수 좌표 $(x^+, y^+)$ 어디에나 놓을 수 있고, 경로가 이 돌을 밟지 않아도 된다.

새 돌을 놓는 모든 방법과 모든 경로 가운데, 가장 긴 도약 길이의 최솟값을 구하여라.

최적 경로	돌을 하나 더 놓았을 때의 최적 경로

첫째 줄에 강의 너비 $w$와 돌의 개수 $n$이 주어진다 ($1 \le w \le 10^9$, $0 \le n \le 1000$).

다음 $n$개 줄에 돌 하나의 좌표 $x_i$, $y_i$가 주어진다 ($0 < x_i < w$, $-10^9 \le y_i \le 10^9$). 같은 점에 놓인 돌은 없다.

가장 긴 도약 길이의 최솟값을 소수점 아래 셋째 자리까지 정확히 출력한다. 답이 반올림 경계에 정확히 걸리는 경우는 없다.