Farmer John đang gặp khó khăn trong việc giúp cây cối phát triển và cần bạn hỗ trợ tưới nước cho chúng đúng cách. Bạn được cho vị trí của \(N\) giọt mưa (\(1 \leq N \leq 100\,000\)) trên mặt phẳng hai chiều, trong đó \(y\) biểu thị độ cao thẳng đứng của giọt mưa và \(x\) biểu thị vị trí của nó trên một trục số một chiều:

Mỗi giọt rơi thẳng xuống dưới (về phía trục \(x\)) với tốc độ 1 đơn vị mỗi giây. Bạn muốn đặt chậu hoa rộng \(W\) của Farmer John ở đâu đó dọc theo trục \(x\) sao cho chênh lệch thời gian giữa giọt mưa đầu tiên và giọt mưa cuối cùng rơi trúng chậu ít nhất là một giá trị \(D\) nào đó (để hoa trong chậu nhận được thật nhiều nước). Một giọt nước rơi đúng vào mép chậu vẫn được tính là rơi trúng chậu.

Cho giá trị \(D\) và vị trí của \(N\) giọt mưa, hãy tính giá trị nhỏ nhất có thể của \(W\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách, \(N\) và \(D\) (\(1 \leq D \leq 1\,000\,000\)).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa tọa độ \((x,y)\) cách nhau bởi dấu cách của giọt mưa \(i\); mỗi giá trị nằm trong khoảng \(0 \ldots 1\,000\,000\).

Dữ liệu ra

In ra một số nguyên duy nhất là chiều rộng nhỏ nhất có thể của chậu hoa. In -1 nếu không thể làm một chậu đủ rộng để hứng mưa trong ít nhất \(D\) đơn vị thời gian.

Ví dụ

4 5
6 3
2 4
4 10
12 15

2

Nguồn

USACO 2012 March Contest, Silver Division — Flowerpot. Tác giả đề: Brian Dean (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=125