题目描述

$\red{Bessie}$参加了爬墙比赛，比赛用的墙宽$\red{30000,}$高$\red{H(1001 <= H <= 30,000)}$。墙上有$\red{F(1 <= F <= 10,000)}$个不同的落脚点$\red{（X，}$$\red{Y）}$。 $\red{（0，}$$\red{0）}$在左下角的地面。所有的落脚点至少相距$\red{300}$。$\red{Bessie}$知道至少有一条路可以上去。

$\red{Bessie}$只能从一个落脚点爬到另一个距离不超过$\red{1000}$的落脚点，她可以向上下左右四个方向爬行。同样地，一旦她到达了一个高度 至少有$\red{H-1000}$的落 脚点，她可以敏捷地爬到墙顶上。$\red{Bessie}$一开始可以在任意一个高度不超过$\red{1000}$的落脚点上。

问$\red{Bessie}$至少攀爬多少次.这里两个点的距离都是欧几里得距离

输入格式

第$\red{1}$行：两个空间分隔的整数，$\red{H}$和$\red{F}$。

第$\red{2...F+1}$行：每行包含两个空格分隔的整数（分别为$\red{X}$和Y），用于描述蹄持。$\red{X}$是距攀爬壁左边缘的距离；$\red{Y}$是距地面的距离。

输出格式

第$\red{1}$行：一个整数是贝西到达攀岩墙顶部必须使用的最小蹄数。

样例

输入样例

3000 5
600 800
1600 1800
100 1300
300 2100
1600 2300

输出样例

3

提示

分别经过$\red{(600,800), (100,1300), (300,2100)}$

输入详细信息：这堵墙有三米高，有五个马蹄。