P6245 [USACO06OPEN] The Climbing Wall S

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

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**.

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 a single integer: the minimum number of moves Bessie needs to reach the top of the climbing wall.

#### 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