#P3416. Moo-cast Broadcast

    ID: 16671 Type: Default 1000ms 256MiB

Moo-cast Broadcast

Moo-cast Broadcast

Farmer John's $N$ cows ($1 \leq N \leq 200$) are setting up an emergency "moo-cast" system to broadcast messages among themselves. Each cow is equipped with a walkie-talkie that has a limited transmission power. A walkie-talkie with power $P$ can only transmit to cows within a distance of $P$ (note that transmission is not necessarily bidirectional).

Cows can relay messages along a series of hops. Determine the maximum number of cows that can be reached by a broadcast originating from a single cow.

Input Format: The first line contains an integer $N$. The next $N$ lines each contain three integers $x_i$, $y_i$, and $P_i$, representing the coordinates and the transmission power of the i-th cow.

Note: A cow A can transmit to cow B if and only if $$ (x_A-x_B)^2+(y_A-y_B)^2 \leq P_A^2. $$

Output Format: Output a single integer representing the maximum number of cows that can be reached by a broadcast, including the originating cow.

inputFormat

The first line contains a single integer $N$, the number of cows. Each of the next $N$ lines contains three space-separated integers: $x_i$, $y_i$, and $P_i$.

outputFormat

Output a single integer, the maximum number of cows that can be reached through the broadcast from one starting cow.

sample

4
1 3 5
5 4 3
7 2 1
6 1 1
3