Background

This problem is a shortened version that ensures the original meaning is not changed.

Problem Description

Bessie wants to climb a wall. The wall has width $30000$ and height $H$. There are $F$ distinct footholds $(X,Y)$ on the wall.

$(0,0)$ is on the ground at the bottom-left corner. Any two footholds are at least $300$ apart. There is at least one path to the top. Each time, Bessie can climb at most $1000$ units of distance, and she can move in any direction.

Once she reaches a foothold whose height is less than $1000$ away from $H$, she can go directly to the top of the wall. Bessie may start on any foothold whose height is at most $1000$. Find the minimum number of moves for Bessie to reach the top.

In this problem, distance means Euclidean distance.

Input Format

The first line contains two integers $H$ and $F$, separated by a space.

Lines $2$ to $F+1$ each contain the coordinates $(X,Y)$ of a foothold, where $X$ is the distance from the left side of the climbing wall, and $Y$ is the distance from the ground.

Output Format

Output a single integer: the minimum number of moves Bessie needs to reach the top of the climbing wall.

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

3

Hint

Sample Explanation

The path goes through $(600,800),(100,1300),(300,2100)$.

Constraints:

$1001\le H\le 3\times 10^4$

$1\le F\le 10^4$

Translated by ChatGPT 5