Problem Description

A vertical stone wall stands in front of Bessie, and she must climb over it.

The wall can be seen as the $xz$ plane. Bessie starts at $(0,0)$. As long as she reaches the position with $z = T$ ( $1 \leq T \leq 200000$ ), the climb is considered successful.

There are $N$ ( $1 \leq N \leq 50000$ ) stones protruding from the wall, which can be used as footholds. If the distances between two footholds in both the $x$ direction and the $z$ direction are no more than $2$, then Bessie can climb from one foothold to the other.

Help Bessie determine whether she can climb over the wall. If she can, find the minimum number of footholds she needs to step on.

Input Format

The first line contains $N$ and $T$.

The next $N$ lines each contain the coordinates $(x,z)$, representing the position of a stone. Here $x \leq 10^6$ and $z \leq T$. It is guaranteed that $(0,0)$ does not appear.

Output Format

If Bessie can climb over the wall, output the minimum number of footholds needed (the starting point is not counted). Otherwise, output $-1$.

5 3
1 2
6 3
4 1
3 2
0 2

4

Hint

One possible route is: (0,0) -> (1,2) -> (3,2) -> (4,1) -> (6,3).

Translated by ChatGPT 5