题目描述

冰川是缓慢流动的巨大冰河，其中遍布被薄雪覆盖的裂缝。毫无防备的徒步者可能踩入裂缝并坠落。为了降低危险，徒步者通常结伴行动，并用粗绳相连：若一人坠落，另一人或许能在安全距离外将其拉住。

今天，你和同伴用绳索连接，准备沿一条给定路线穿越冰川。你们将以相同速度沿完全相同的路线前进：第一名行者先出发；当他沿路线领先第二名行者恰好 $s$ 米时，第二名行者开始沿其足迹前进。

如果路线是一条直线，那么两人之后始终相距恰好 $s$ 米。但由于路线会不断转弯、折返，两人的欧氏距离可能小于 $s$。

第二个样例中路线的俯视示意图

请计算在两人都位于路线上的时间段内，他们之间曾达到的最小欧氏距离。

输入格式

第一行包含一个实数 $s$，表示两人沿路线方向的间隔距离，单位为米：

第二行包含一个整数 $n$，表示路线上的折点数量：

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示路线上的第 $i$ 个点：

任意两个相邻点互不相同，但路线可以自交，也可以重复经过同一位置。

保证路线总长度至少为 $s$。

输出格式

输出两名行者之间的最小欧氏距离。

只考虑第二名行者开始行走之后、第一名行者到达终点之前的时间。第一名行者结束后的时间以及第二名行者开始前的时间均忽略。

答案的绝对误差或相对误差不得超过 $10^{-4}$。

样例 1

输入

5
4
20 0
10 0
10 10
0 10

输出

3.5355339

样例 2

输入

3.16227766
9
-2 4
2 4
3 1
4 4
5 1
6 4
10 2
6 1
7 4

输出

1