Description

兔斯基待在一条无限长的路上,路上点的编号是…,-3,-2,-1,0,1,2,3….现在兔斯基在0的位置上.她想跳到她朋友那里去玩,她朋友在1000000001处. 当她处在x处时,可以有两个跳法,小跳和大跳:

小跳: 跳到x+2 或者 x-2

大跳: 跳到x+L 或者 x-L (其中L是一个给定的常数)

但是,路途上有很多的陷阱, 兔斯基不能跳到有陷阱的点上.给你一些区间[ai,bi],这些区间上的点都是有陷阱的点, 兔斯基都不能跳上去,并且现在让你编程求出兔斯基从0点跳到她朋友那里需要最少的大跳步数.如果兔斯基永远都跳不到,那么输出-1

Input

输入包含多组数据. 每组数据第一行包含两个整数N和L,分别表示陷阱区间的个数,大跳的步长.(0<=N<=50,3<=L<=1000000000). 接下来有N行,每行包含两个数字a,b(1<=a< b<=1000000000).表示[a,b]上的点都是陷阱.所有区间不重叠.

Output

输出兔斯基需要的最少的大跳个数 或者 -1

Sample

Input

1 3
1 2

1 4
1 2

1 3
2 3

Output

1
-1
3

Source: zjut_DD