题目描述

最近流行攀岩运动,类似的一种比赛是在一个宽 $30000$ 毫米,高 $H$ 毫米的墙上,有 $F$ 个支撑点可供攀登用，登上顶者为获胜。支撑点用坐标 ( $x,y$ ) 表示，墙的左下角坐标为 ( $0,0$ )。为了不太密集，每两个支撑点至少相距 300 毫米。

Bessie 知道她可以从一个支撑点上下左右任意地向另一个支撑点运动，但要求两支撑点之间不能超过 $1000$ 毫米才可以。并且如果她爬到 $H-1000$ 高度之上时，就可以灵活地爬上去直接登顶了。

Bessie 开始的时可以从任何一个高度不超过 $1$ 米的支撑点开始，即 $x$ 坐标任意，$y$ 坐标 $\le 1000$ 毫米的支撑点。

现在 Bessie 请你帮她计算最少要经过多少个支撑点就可以攀登到顶。

输入格式

第 1 行，两个整数 $H$ 和 $F$ ( $1001 \le H \le 30000$，$1 \le F \le 10000$ )

第 2 行到第 $F+1$ 行，每行两个整数 $x$，$y$，表示一个支撑点的坐标。$x$ 表示距左边的距离，$y$ 表示距下面的距离。

输出格式

只有一个整数，表示最少要用的支撑点个数。

样例

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

3

样例说明：攀爬的次序是第 1 个，第 3 个，第 4 个支撑点。