[Usaco2006 Open]The Climbing Wall 攀岩

县集市上最受欢迎的项目之一是攀岩。Bessie 想提前规划攀登路线，需要你帮助她计算到达墙顶所需使用的最少落脚点数。

攀岩墙宽 $3\times 10^4$ 毫米，高 $H$ 毫米。墙上有 $F$ 个落脚点，每个落脚点都由唯一的坐标 $(X,Y)$ 表示，单位为毫米。坐标原点 $(0,0)$ 位于墙的左下角。任意两个落脚点之间的欧几里得距离至少为 $300$ 毫米。

Bessie 每次可以从当前落脚点移动到另一个欧几里得距离不超过 $1000$ 毫米的落脚点，移动方向不限。当她到达纵坐标至少为 $H-1000$ 的落脚点时，就可以从该处登上墙顶。她可以从任意一个纵坐标不超过 $1000$ 的落脚点开始攀登。

已知至少存在一条能够到达墙顶的路线，请求出 Bessie 到达墙顶所需使用的最少落脚点数。

输入格式

第一行包含两个以空格分隔的整数 $H$ 和 $F$，分别表示攀岩墙的高度和落脚点数量。

接下来 $F$ 行，每行包含两个以空格分隔的整数 $X$ 和 $Y$，表示一个落脚点到墙左边缘和地面的距离。

输出格式

输出一个整数，表示 Bessie 到达墙顶所需使用的最少落脚点数。

样例输入

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

样例输出

3

样例解释

Bessie 可以依次经过落脚点 $(600,800)$、$(100,1300)$ 和 $(300,2100)$，共使用 $3$ 个落脚点后到达墙顶。

数据范围

• $1001\le H\le 3\times 10^4$；
• $1\le F\le 10^4$；
• 攀岩墙的宽度为 $3\times 10^4$ 毫米；
• 所有落脚点的坐标互不相同；
• 任意两个落脚点之间的欧几里得距离至少为 $300$ 毫米；
• 保证至少存在一条能够到达墙顶的路线。

来源与许可

本题为 USACO 2006 Open 试题「攀岩」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

3