Đó là một ngày hè nóng nực và cô bò Bessie cảm thấy khá lười biếng. Cô muốn chọn một vị trí trong cánh đồng để có thể tiếp cận nhiều cỏ ngon nhất có thể mà chỉ phải đi một quãng ngắn.

Cánh đồng của Bessie có \(N\) cụm cỏ (\(1 \le N \le 100\,000\)). Cụm cỏ thứ \(i\) chứa \(g_i\) đơn vị cỏ (\(1 \le g_i \le 10\,000\)) và nằm tại một điểm \((x_i,y_i)\) riêng biệt trên cánh đồng (\(0 \le x_i,y_i \le 1\,000\,000\)). Bessie muốn chọn một điểm trên cánh đồng làm vị trí ban đầu (điểm này có thể trùng với một cụm cỏ, thậm chí có thể có tọa độ không nguyên) sao cho lượng cỏ nằm cách vị trí đó không quá \(K\) bước là lớn nhất (\(1 \le K \le 2\,000\,000\)).

Khi Bessie đi một bước, cô di chuyển \(1\) đơn vị về phía bắc, nam, đông hoặc tây so với vị trí hiện tại. Ví dụ, để đi từ \((0,0)\) đến \((3,2)\) cần tổng cộng \(5\) bước. Bessie không nhất thiết phải đi những bước có độ dài nguyên; chẳng hạn, tổng cộng \(1\) bước có thể được chia thành nửa đơn vị về phía bắc và nửa đơn vị về phía đông.

Hãy giúp Bessie xác định lượng cỏ lớn nhất mà cô có thể tiếp cận nếu chọn vị trí ban đầu tối ưu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(g_i\), \(x_i\) và \(y_i\), mô tả cụm cỏ thứ \(i\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le g_i \le 10\,000\).
• \(0 \le x_i,y_i \le 1\,000\,000\) và các điểm \((x_i,y_i)\) đôi một khác nhau.
• \(1 \le K \le 2\,000\,000\).

Dữ liệu ra

In ra lượng cỏ lớn nhất Bessie có thể tiếp cận trong phạm vi \(K\) bước nếu chọn vị trí ban đầu tối ưu.

Ví dụ

4 3
7 8 6
3 0 0
4 6 0
1 4 2

8

Nguồn

USACO 2014 March Contest, Gold — The Lazy Cow

Tác giả: Brian Dean, 2014.