Bò Lười (Gold)

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 $\le 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\le N\le 100000$
• $1\le g_i\le 10000$
• $0\le x_i,y_i\le 1000000$
• $1\le K\le 2000000$

Ví dụ