Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Rà phá mìn còn sót lại sau chiến tranh là nhiệm vụ rất khó khăn và đầy hiểm nguy của các chiến sĩ công binh. Ban chỉ huy trung đoàn công binh X vừa nhận nhiệm vụ phá một bãi mìn lớn. Bằng nghiệp vụ cao và với tinh thần dũng cảm, các chiến sĩ của trung đoàn đã lên được sơ đồ của bãi mìn. Có tất cả n quả mìn, được đánh số từ 0 đến n–1. Trên mặt phẳng toạ độ, vị trí của quả mìn thứ i có toạ độ là (x_i, y_i), i = 0, 1, …, n–1. Để phá toàn bộ bãi mìn, cần đặt thiết bị kích nổ các quả mìn. Mỗi thiết bị kích nổ sẽ được đặt ở đúng vị trí của một quả mìn và sẽ được kích hoạt từ xa để đảm bảo an toàn cho các chiến sĩ công binh. Khi một quả mìn được kích nổ, sức công phá của nó có thể kích nổ các quả mìn trong phạm vi bán kính nhất định và khi các quả mìn này nổ chúng lại tiếp tục kích nổ những quả mìn khác trong phạm vi bán kính kích nổ của chúng,… Các chiến sĩ công binh cũng đã xác định được ri là bán kính công phá của quả mìn ở vị trí i, nghĩa là nếu quả mìn i được kích nổ thì mọi quả mìn có toạ độ nằm trong hình tròn (kể cả trên biên) tâm tại (xi, yi) bán kính ri sẽ đều bị kích nổ. Thiết bị kích nổ từ xa khá đắt tiền, do đó vấn đề đặt ra là tìm cách đặt một số ít nhất thiết bị kích nổ để có thể phá huỷ toàn bộ bãi mìn.

Yêu cầu: Dựa vào sơ đồ vị trí của các quả mìn và bán kính kích nổ của chúng, hãy giúp các chiến sĩ công binh giải quyết vấn đề đặt ra.     

Input

• Dòng đầu tiên chứa số nguyên dương n là số lượng quả mìn (n ≤ 3´10⁵);
• Dòng thứ i trong số n dòng tiếp theo chứa ba số nguyên x_i, y_i, r_i được ghi cách nhau bởi dấu cách, trong đó (x_i, y_i) là toạ độ còn r_i là bán kính kích nổ của quả mìn thứ i (–10⁶ ≤ xi, yi ≤ 10⁶, 0 < ri ≤ 10⁶, i = 0, 1, …, n–1). Chú ý là có thể có những quả mìn xuất hiện tại cùng một vị trí.

Output

• Một số nguyên dương k là số lượng thiết bị kích nổ ít nhất cần sử dụng.

Example

Input:

5

-15 4 10

12 4 8

-10 -4 8

2 10 16

18 10 8

Output:

2

Giải thích ví dụ: Minh hoạ cho ví dụ được cho trong hình vẽ dưới đây. Ta có thể đặt 2 thiết bị kích nổ tại vị trí quả mìn 0 và quả mìn 3 để kích nổ bãi mìn.