[Usaco2004 Open]Cave Cows 4 洞穴里的牛之四

时间限制:1s      空间限制:128MB

题目描述

    一道竖直的石墙横在贝茜前面,她必须越过去.
    石墙可以看成一个xz平面,贝茜开始的时候在(0,0),只要她到达z=T(1≤T≤200000)的位置,就算翻越成功.
    墙上有N(1≤N≤50000)块石头突出,成为贝茜的落蹄石.如果两个落蹄石之间z方向和名方向的距离均不超过2,那贝茜就可以之它们之间攀越. 帮助贝茜计算她是否能够翻越石墙,如果可以,最少需要踩多少块落蹄石.


输入格式

    第1行输入N和T;接下来N行,每行输入坐标(x,z),表示一个石头的位置.其中x∈[0,10^6],z∈[0,T],(0,0)不会出现.


输出格式

 
    如果可以翻越则输出最少需要的落蹄石数(起点不计入),否则输出-1.


样例输入

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

样例输出

4

提示

没有写明提示


题目来源

Orange

Menuappsclose