Chậu hoa

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ giọt mưa rơi thẳng đứng với vận tốc 1 đơn vị/giây. Giọt thứ $i$ bắt đầu tại tọa độ $(x_{i}, y_{i})$ và chạm đất sau $y_{i}$ giây.

Đặt một cái chậu hoa có độ rộng $W$ tại vị trí $[a, a + W]$ trên trục hoành. Chậu bắt được giọt $i$ nếu $a \leq x_{i} \leq a + W$ . Tìm độ rộng $W$ nhỏ nhất sao cho tồn tại một vị trí đặt chậu mà hiệu thời gian giữa giọt đầu tiên và giọt cuối cùng chạm vào chậu $\geq D$ .

Nếu không có độ rộng nào thỏa mãn, in $- 1$ .

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $D$ .
$N$ dòng tiếp: Mỗi dòng chứa hai số nguyên $x_{i}$ và $y_{i}$ .

Dữ liệu ra

Một số nguyên — độ rộng $W$ nhỏ nhất, hoặc $- 1$ nếu không thể.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq D \leq 10^{6}$
$0 \leq x_{i}, y_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
4 5 6 3 2 4 4 10 12 15	2	Đặt chậu $[4, 6]$ : bắt giọt $(4, 10)$ và $(6, 3)$ , hiệu thời gian $= 10 - 3 = 7 \geq 5$ .
30 100 67 102 ...	-1	Mọi tập giọt có thể bắt đều không đạt hiệu thời gian 100.

Bình luận

Không có bình luận tại thời điểm này.