TAP2015A - AM FM

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

Amelia has decided to retire from programming competitions and move to a more peaceful place, away from the noisy city. She dreams of sitting in front of her house to see the sunset over the countryside, while listening on the radio to one of her beloved soap operas. However, before fulfilling her dreams she must solve one last problem, which consists in choosing where she should move.

The countryside where Amelia wants to move to is very large and flat, so much so that it can be represented by an infinite plane on which we imagine a Cartesian coordinate system (X, Y). In this countryside there are N radio stations numbered 1 through N. The i-th radio station transmits its signal from an antenna placed at point (Xi, Yi), having said signal a range of Ri. This radio station can be tuned in to from any point (X, Y) whose distance to the antenna is less or equal to the corresponding range, i.e. satisfying:

(X - Xi)2 + (Y - Yi)2 ≤ Ri2

The signals from different radio stations can overlap, but will never interfere with each other. In order to listen to as many soap operas as possible, Amelia wants to place her house at some point within the range of the maximum possible number of radio stations. Now Amelia wants to know, given the description of the countryside, what is the maximum number of radio stations she will be able to tune in to as she sees the sunset over the countryside sitting in front of her house.

 

Amelia has decided to retire from programming competitions and move to a more peaceful place, away from the noisy city. She dreams of sitting in front of her house to see the sunset over the countryside, while listening on the radio to one of her beloved soap operas. However, before fulfilling her dreams she must solve one last problem, which consists in choosing where she should move.
The countryside where Amelia wants to move to is very large and flat, so much so that it can be represented by an infinite plane on which we imagine a Cartesian coordinate system (X, Y). In this countryside there are N radio stations numbered 1 through N. The i-th radio station transmits its signal from an antenna placed at point (X[i], Y[i]), having said signal a range of R[i]. This radio station can be tuned in to from any point (X, Y) whose distance to the antenna is less or equal to the corresponding range, i.e. satisfying:
(X - X[i])² + (Y - Y[i])² ≤ R[i]²

The signals from different radio stations can overlap, but will never interfere with each other. In order to listen to as many soap operas as possible, Amelia wants to place her house at some point within the range of the maximum possible number of radio stations. Now Amelia wants to know, given the description of the countryside, what is the maximum number of radio stations she will be able to tune in to as she sees the sunset ove

 

 

Amelia has decided to retire from programming competitions and move to a more peaceful place, away from the noisy city. She dreams of sitting in front of her house to see the sunset over the countryside, while listening on the radio to one of her beloved soap operas. However, before fulfilling her dreams she must solve one last problem, which consists in choosing where she should mov

Input

There are multiple test cases in the input file. For each test case, the first line contains an integer N representing the number of radio stations in the countryside (1 ≤ N ≤ 100). Each of the following N lines contains three integers Xi, Yi and Ri representing respectively the coordinates of the antenna and the range of the i-th radio station (-1000 ≤ Xi, Yi ≤ 1000 and 1 ≤ Ri ≤ 1000 for i = 1, 2, ..., N).

 

Output

For each test case, print one line containing an integer representing the maximum number of radio stations Amelia will be able to tune in to if she optimally chooses where to move to.

 

Example

Input:
5
-1 0 2
1 0 2
0 -2 1
0 0 1
0 2 1

Output:
4


Added by:Fidel Schaposnik
Date:2015-10-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Argentinian Programming Tournament 2015