Nông dân John (FJ) đang gặp vấn đề trong việc trồng cây và anh ta cần bạn giúp tưới nước cho cây một cách đúng đắn. Bạn được cho vị trí của giọt nước mưa trên mặt phẳng hai chiều với trục Oy là chiều thẳng đứng còn trục Ox là chiều nằm ngang:
Tất cả các giọt nước mưa đều rơi thẳng xuống dưới (xuống trục Ox) với vận tốc đơn vị dài/ giây. Bạn cần giúp FJ thiết kế một cái chậu hoa chiều rộng đặt dọc theo trục Ox sao cho sự khác nhau giữa thời điểm giọt mưa đầu tiên rơi vào chậu hoa và thời điểm giọt mưa cuối cùng rơi vào chậu ít nhất phải là . Những giọt mưa rơi vào cạnh của chậu hoa cũng được tính là rơi vào trong chậu.
Cho biết giá trị của và vị trí các giọt nước mưa. Hãy xác định giá trị nhỏ nhất có thể có của .
Dữ liệu vào:
Dòng đầu ghi hai số nguyên ;
dòng sau, mỗi dòng ghi hai số nguyên là toạ độ một giọt nước mưa. Các toạ độ có giá trị trong khoảng từ đến .
Dữ liệu ra:
Ghi ra một số nguyên là giá trị nhỏ nhất chiều rộng của chậu hoa hoặc in ra nếu không thể thiết kế được một chậu nào như vậy.
Ví dụ:
Dữ liệu vào:
4 5
6 3
2 4
4 10
12 15
Dữ liệu ra:
2
Giải thích:
Chiều rộng nhỏ nhất là và đặt tại toạ độ từ đến . Khi đó chậu hứng được hai giọt và . Chênh lệch thời gian là .
