Cho ~n~ cửa hàng bán cửa trên trục tọa độ ~Ox~, mỗi cửa hàng có cửa ra vào đi từ ~l_i~ đến ~r_i~ ~(l_i<r_i)~ trên trục tọa độ. Ban đầu, các cửa của cửa hàng đều đang đóng.</p>

Vào mùa cua đang thịnh hành, các cửa hàng bán cửa cũng sẽ bán cua, nên ta sẽ gọi các cửa hàng tắt là cua-cửa. Cách mở cửa của cua-cửa sẽ được miêu tả như sau:

• Vào mỗi giây các hàng cua-cửa sẽ được mở cửa, bắt đầu từ hàng cuối cùng, tức hàng ~n~, và kết thúc ở hàng ~1~.

• Vào giây hàng cua-cửa thứ ~i~ được mở, mọi cửa của các hàng mở trước cửa hàng thứ ~i~ sẽ mở rộng cửa để đón khách bằng cách dịch lề trái của cửa sang trái một đơn vị. Nói cách khác, với mọi ~j>i~, ~l_j~ sẽ giảm bởi ~1~.

• Vào giây hàng cua-cửa thứ ~i~ được mở, các cặp ~(i,j)~ ~(i \le j)~ sẽ lập tức được coi là tình địch nếu hai cửa của hai cửa hàng có đỉnh chung với nhau. Những cửa hàng cua-cửa được phép có nhiều tình địch. Ta chỉ quan tâm đến những cặp trở thành tình địch ngay trong thời điểm mở cửa của cửa hàng được đánh số bé hơn.

Trong những cặp ~(i,j)~ có tình địch như được nêu trên, nếu ~i \oplus j>x~ (~\oplus~ là phép XOR) thì sự tình địch của các cặp đó sẽ bị hủy bỏ. Hãy tìm cặp ~(i,j)~ có giá trị ~j-i~ lớn nhất, thỏa mãn hai cửa của cửa hàng cua-cửa đó có tình địch với nhau tại thời điểm cửa hàng thứ ~i~ được mở.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~x~ ~(n \le 100000, x \le 10^9)~.

Dòng thứ ~i+1~ ~(1 \le i \le n)~ chứa ~2~ số nguyên dương ~l_i~ và ~r_i~ ~(1 \le l_i, r_i \le 10^9)~.

Output

In ra một số duy nhất là đáp án của bài toán.

Scoring

Sample Input 1

10 6
5 10
8 9
12 18
19 20
22 23
19 20
24 31
29 30
29 35
37 39

Sample Output 1

3