The Climbing Wall

Interview

Time limit2sMemory limit512 MB

Summary

Given holds on a wall, find the fewest holds Bessie must step on to climb from within 1000 mm of the ground to within 1000 mm of the top, moving only between holds at most 1000 mm apart.

Level: Medium6 of 10
Topics: Graph, BFS, Shortest path, Geometry
Solved: No attempts yet

Problem

The most popular attraction at the county fair is the climbing wall. Bessie wants to plan her route up the wall before she starts.

The wall is 30000 millimeters wide and $H$ ( $1001 \le H \le 30000$ ) millimeters high. It holds $F$ ( $1 \le F \le 10000$ ) hoof holds, each given as a coordinate $(X, Y)$ in millimeters, and no two holds share a position. The coordinate $(0, 0)$ is the ground at the left edge of the wall. A cow cannot use holds that sit too close together, so the distance between any two holds is at least 300 millimeters. At least one way up exists.

Bessie climbs by stepping on one hold at a time. She can move from one hold to another only when the straight line distance between them is at most 1000 millimeters, and the move may go up, down, right, left, or any mix of those. Once she reaches a hold that is at least $H - 1000$ millimeters above the ground, she can climb from there onto the platform on top of the wall. She starts on any hold whose $Y$ coordinate is at most 1000 millimeters.

Given the height of the wall and the positions of the holds, find the smallest number of holds Bessie has to step on to reach the top.

Input

The first line contains $H$ and $F$ separated by a space.
Each of the next $F$ lines contains the $X$ and $Y$ coordinates of one hold, separated by a space. $X$ is the distance from the left edge of the wall and $Y$ is the height above the ground, with $0 \le X \le 30000$ and $0 \le Y \le H$ .

Output

Print the smallest number of holds Bessie must step on to reach the top of the wall. The count includes the hold she starts on and the last hold she uses before the platform.

Examples5

Example 1

Input

Expected output

Example 2
Input
```
1500 1
15000 700
```
Expected output
```
1
```
Example 3
Input
```
3000 3
0 1000
600 1800
1200 2600
```
Expected output
```
3
```
Example 4
Input
```
3001 3
0 1000
0 2001
700 1500
```
Expected output
```
3
```

Example 5

Input

Expected output