Ghost Busters

Time limit1sMemory limit128 MB

Summary

A ray from the origin inside the octant X,Y,Z >= 0 must be aimed to graze (touch) as many spheres as possible; report the maximum count.

Level: Medium7 of 10
Topics: Geometry, Math, Brute force, Implementation
Solved: No attempts yet

Problem

The Ghost Busters team has upgraded their Ecto-1 with a powerful proton gun and an automatic targeting system, and you have been hired to write a prototype for the targeting software.

Each ghost is detected as a floating sphere, given by the coordinates of its center and its radius. The proton gun fires from the origin $(0, 0, 0)$ in any direction inside the octant $X \ge 0,\ Y \ge 0,\ Z \ge 0$ . It emits a single ray that travels in a straight line from the origin; even a graze from this ray destroys a ghost, and one ray can destroy an unlimited number of ghosts lying along its path.

Determine the maximum number of ghosts that can be destroyed with a single shot fired from the origin.

Input

The first line contains the number of detected ghosts $N$ ( $0 \le N \le 100$ ).

Each of the next $N$ lines describes one ghost with four integers $X_i$ , $Y_i$ , $Z_i$ , $R_i$ separated by spaces, where $(X_i, Y_i, Z_i)$ is the center and $R_i$ is the radius. It is guaranteed that $1 \le X_i, Y_i, Z_i \le 10000$ and $1 \le R_i \le \min(X_i, Y_i, Z_i)$ .

Ghosts may overlap, be contained in one another, or coincide.

Output

Print a single integer: the maximum number of ghosts that can be destroyed with one shot.

Examples2

Example 1
Input
```
2
1200 1200 3900 300
160 160 820 60
```
Expected output
```
2
```

Example 2

Input

13
1200 1200 3900 300
160 160 820 60
100 10 10 10
10 100 10 10
10 10 100 10
10 10 10 10
50 50 50 10
100 100 75 20
100 75 100 20
75 100 100 20
3000 4000 7000 2600
100 1000 1000 50
1000 100 1000 100

Expected output