Bessie's Stone Climb

Bessie faces a vertical stone wall represented by the xz plane. She starts at (0, 0) and must reach any position with z = T (where \(1 \le T \le 200000\)) in order to successfully cross the wall.

The wall has \(N\) protruding stones (\(1 \le N \le 50000\)), each acting as a foothold. Each stone is located at an integer coordinate \((x, z)\). Bessie is allowed to move from one foothold to another if and only if the absolute difference in the x coordinate and the absolute difference in the z coordinate are both at most 2, i.e. for two footholds \((x_1, z_1)\) and \((x_2, z_2)\):

\[ |x_1 - x_2| \le 2 \quad \text{and} \quad |z_1 - z_2| \le 2. \]

Bessie starts at (0, 0) (which is not counted as a foothold) and she may step onto any stone if the move from her current position (or stone) meets the above condition. Moreover, when Bessie is on a foothold (or at the starting point) with a z coordinate such that \(T - z \le 2\), she can directly exit the wall without stepping onto any further stone.

Your task is to help Bessie determine if it is possible for her to cross the wall, and if so, to compute the minimum number of stones she must step on (excluding the starting position). If it is impossible for her to cross, print -1.

inputFormat

The first line contains two integers, T and N, separated by a space, where T is the target z coordinate and N is the number of stones on the wall.

Each of the following N lines contains two space‐separated integers x and z, representing the coordinates of a stone.

Note: It is guaranteed that \(1 \le T \le 200000\) and \(1 \le N \le 50000\).

outputFormat

Output a single integer: the minimum number of stones Bessie must step on to cross the wall. If it is impossible for her to cross, output -1.

sample

5 3
1 2
0 3
2 4

2