Bác nông dân John đang gặp khó khăn trong việc chăm sóc cây cối và cần sự giúp đỡ của bạn để tưới nước cho chúng đúng cách. Bạn được cho vị trí của ~N~ hạt mưa ~(1 \le N \le 100{,}000)~ trên một mặt phẳng 2D. Trong đó:

• ~y~: Đại diện cho độ cao thẳng đứng của hạt mưa.

• ~x~: Đại diện cho vị trí của nó trên một trục số nằm ngang.

Mỗi hạt mưa rơi thẳng xuống (về phía trục ~x~) với tốc độ ~1~ đơn vị mỗi giây. Bạn muốn đặt một chiếc chậu hoa có độ rộng ~W~ của bác John ở đâu đó trên trục ~x~, sao cho khoảng chênh lệch thời gian giữa hạt mưa đầu tiên rơi vào chậu và hạt mưa cuối cùng rơi vào chậu ít nhất là ~D~ (để hoa trong chậu nhận được đủ nước).

Lưu ý: Một hạt mưa rơi đúng vào cạnh của chậu hoa vẫn được tính là rơi trúng vào chậu.

Yêu cầu: Với giá trị ~D~ và vị trí của ~N~ hạt mưa, hãy tính giá trị nhỏ nhất có thể của độ rộng ~W~.

Input

• Dòng ~1~: Hai số nguyên cách nhau bởi dấu cách, ~N~ và ~D~ ~(1 \le D \le 1{,}000{,}000)~.

• Dòng ~2..1+N~: Mỗi dòng chứa tọa độ ~(x,y)~ của hạt mưa thứ ~i~, mỗi giá trị nằm trong khoảng ~0 \dots 1{,}000{,}000~.

Output

• Một số nguyên duy nhất là độ rộng nhỏ nhất có thể của chậu hoa.

• Xuất ra ~-1~ nếu không thể xây dựng được chậu hoa nào đủ rộng để hứng nước mưa trong khoảng thời gian ít nhất là ~D~.

Sample Input 1

4 5
6 3
2 4
4 10
12 15

Sample Output 1

2

Notes

Có ~4~ hạt mưa tại các vị trí ~(6,3)~, ~(2,4)~, ~(4,10)~ và ~(12,15)~. Thời gian mưa rơi vào chậu phải ít nhất là ~5~ đơn vị thời gian.

Một chậu hoa có độ rộng là ~2~ là điều kiện cần và đủ, vì nếu ta đặt chậu từ ~x=4 \dots 6~, nó sẽ hứng được hạt mưa số ~1~ (tại ~x=6, y=3~) và hạt mưa số ~3~ (tại ~x=4, y=10~). Tổng thời gian chênh lệch là ~10-3=7~ (lớn hơn hoặc bằng ~D=5~).