P5099 [USACO04OPEN] Cave Cows 4

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.

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.

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

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