Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Nhà cung cấp dịch vụ viễn thông Mobi đã khảo sát số lượng người sẽ dùng dịch vụ trên một con đường thẳng mới được xây dựng và đánh dấu lại những vị trí trên con đường này. Đầu con đường được đánh tọa độ bắt đầu từ 0. Tại vị trí có tọa độ ~X~ (~X~ nguyên dương) có số lượng người sẽ sử dụng dịch vụ là ~Y~. Trước mắt, nhà cung cấp dịch vụ cần đặt một trạm phát sóng có bán kính phủ sóng là ~K~ đơn vị chiều dài để phủ sóng cho một số người sử dụng dịch vụ trên con đường này.

Yêu cầu: Bạn hãy xác định vị trí đặt trạm phát sóng (tọa độ nguyên dương) sao cho trạm có thể phục vụ được số lượng người sử dụng nhiều nhất có thể.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên ~N~ và ~K~ ~(0 \lt N \le 10^6,\ 0 \lt K \le 2 \cdot 10^6)~, trong đó ~N~ là số điểm dân cư đã được đánh dấu, ~K~ là bán kính phủ sóng của trạm.
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ ~(i = 1..N)~ ghi hai số nguyên ~X~ và ~Y~ cho biết tại vị trí ~X~ có số lượng người dùng là ~Y~ ~(0 \le X \le 10^6,\ 0 \le Y \le 10^4)~. Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Kết quả

• Một số nguyên cho biết số người dùng nhiều nhất sẽ được phục vụ.

Sample Input 1

4 3
7 4
15 10
2 2
1 5

Sample Output 1

11

Giải thích

Chọn vị trí đặt trạm phủ sóng tại ~X = 4~. Như vậy có thể phủ sóng đến các vị trí có toạ độ ~1, 2, 7~. Số lượng người sử dụng lớn nhất là ~11~.

Nguồn: OLP 30/4 Khối 10 (CLAOJ).