UOJ Logo 黑暗爆炸OJ

DARKBZOJ

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

Statistics 下载数据

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

4

Hint

Source

Orange