Bessie Wall Climbing

Bessie wants to climb a wall of width \(30000\) and height \(H\). There are \(F\) different footholds on the wall at distinct coordinates \((X,Y)\). The coordinate \((0,0)\) is at the bottom left (ground). Any two footholds are at least \(300\) units apart. It is guaranteed that there is at least one way for Bessie to reach the top.

Bessie can move at most \(1000\) units (Euclidean distance) in a single move, and she can move in any direction. Her starting foothold can be chosen arbitrarily among those at a height not exceeding \(1000\). Once Bessie reaches a foothold where the remaining vertical distance to the top is less than \(1000\), she can directly jump to the top in one final move.

Determine the minimum number of moves required for Bessie to reach the top of the wall using the footholds.

inputFormat

The first line contains two integers \(H\) and \(F\) -- the height of the wall and the number of footholds.

Each of the next \(F\) lines contains two integers \(X\) and \(Y\) representing the coordinates of a foothold.

outputFormat

Output a single integer: the minimum number of moves required for Bessie to reach the top of the wall. If it is impossible, output -1.

sample

4000 4
0 500
0 1400
0 2300
0 3200

4