Cụm Giao Hàng Viettel Post

Mô tả

Tết Nguyên Đán đang đến gần, khối lượng hàng hóa tại mạng lưới Viettel Post tăng đột biến. Để tối ưu tuyến đường, điều độ viên cần phân cụm các trạm giao hàng trên bản đồ thành từng nhóm: hai trạm được xếp vào cùng một cụm nếu chúng giao cùng một loại hàng hóa và khoảng cách Manhattan giữa chúng không vượt quá bán kính phục vụ r mét. Một trạm có thể giao hàng cho trạm khác trong cụm qua các trạm trung gian, miễn là mỗi bước nhảy đều thỏa điều kiện trên.

Nhiệm vụ của bạn là cho biết với cấu hình các trạm hiện tại, có thể thiết lập nhiều nhất bao nhiêu cụm giao hàng độc lập.

Đầu vào

• Dòng thứ nhất chứa hai số nguyên n (số trạm) và r (bán kính phục vụ, tính bằng mét).
• n dòng tiếp theo, mỗi dòng chứa ba giá trị: loai (chuỗi ký tự thường, tên loại hàng), x, y (tọa độ của trạm trên bản đồ, tính bằng mét).

Đầu ra

• Một số nguyên duy nhất là số cụm giao hàng tối đa.

Ràng buộc

• 1 ≤ n ≤ 2000
• 0 ≤ r ≤ 2·10^6
• 0 ≤ |x|, |y| ≤ 10^6
• Độ dài chuỗi loai từ 1 đến 20 ký tự.

Ví dụ

Đầu vào:

5 100 qua 0 0 qua 80 0 qua 200 0 giay 0 0 giay 0 80

Đầu ra:

3

Giải thích:

• Trạm 1 (qua) và Trạm 2 (qua) cách nhau 80m ≤ 100m, cùng loại 'qua' nên thuộc cùng cụm.
• Trạm 3 (qua) cách Trạm 2 là 120m > 100m, không kết nối được, nên Trạm 3 tự thành một cụm riêng.
• Trạm 4 (giay) và Trạm 5 (giay) cùng đứng tại khu vực cách 80m ≤ 100m, lập thành một cụm.
• Tổng cộng có 3 cụm giao hàng.