Bò Lười

Đ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

Trên một trục số có $N$ đám cỏ, đám cỏ thứ $i$ nằm ở vị trí $x_{i}$ và có $g_{i}$ đơn vị cỏ. Một con bò đứng ở một vị trí bất kỳ trên trục số và có thể di chuyển tối đa $K$ bước (sang trái hoặc phải). Con bò có thể ăn tất cả cỏ trong phạm vi $K$ bước từ vị trí đứng.

Hãy tìm vị trí đứng tối ưu để con bò ăn được nhiều cỏ nhất. In ra tổng lượng cỏ lớn nhất con bò có thể ăn được.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $K$ .
$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $g_{i}$ và $x_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất — tổng lượng cỏ lớn nhất có thể ăn được.

Ràng buộc

$1 \leq N \leq 100 000$
$1 \leq g_{i} \leq 10 000$
$0 \leq x_{i} \leq 1 000 000$
$1 \leq K \leq 2 000 000$

Ví dụ

Input	Output	Giải thích
4 3 4 7 10 15 2 2 5 1	11	Đứng ở vị trí $x = 4$ , cỏ ở các vị trí $x = 1$ , $x = 2$ , $x = 7$ đều trong tầm với ( $K = 3$ bước). Tổng cỏ = $5 + 2 + 4 = 11$ .

Bình luận

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