Bò Lười (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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 phẳng tọa độ có $N$ đám cỏ, đám cỏ thứ $i$ nằm ở vị trí $(x_{i}, y_{i})$ và có $g_{i}$ đơn vị cỏ. Một con bò chọn một vị trí bất kỳ (có thể không nguyên) trên mặt phẳng để đứng, và có thể ăn tất cả cỏ trong phạm vi khoảng cách Manhattan $\leq K$ từ vị trí đứng.

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

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 ba số nguyên $g_{i}$ , $x_{i}$ , $y_{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}, y_{i} \leq 1 000 000$
$1 \leq K \leq 2 000 000$

Ví dụ

Input	Output	Giải thích
4 3 7 8 6 3 0 0 4 6 0 1 4 2	8	Đứng ở vị trí $(3, 0)$ , con bò ăn được cỏ ở $(0, 0)$ , $(6, 0)$ và $(4, 2)$ với tổng $3 + 4 + 1 = 8$ . Đám cỏ $(8, 6)$ nằm ngoài tầm với.

Bình luận

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