## LCC/Moose '19 Contest 2 J5 - Evan's Wrath

You are given \(N\) spheres in three-dimensional space by Evan. Each sphere is centered at \((x_i, y_i, z_i)\) and has a radius of \(r_i\). Two spheres intersect if there is a non-zero volume that overlaps. This means that two spheres that *touch* are not considered intersecting.

Out of the \(N\) spheres, you want to choose a subset \(S\) of spheres, such that the no pair of spheres intersect one other, and \(S\) contains the most spheres.

How many spheres are in the largest subset?

#### Input Specification

The first line will contain the integer \(N\) \((1 \le N \le 22)\).

The next \(N\) lines will each contain four integers, \(x_i, y_i, z_i, r_i\) \((|x_i|, |y_i|, |z_i|, r_i \le 10^8)\).

#### Output Specification

Output the size of the largest subset \(S\), such that no pair of spheres in the subset intersects one another.

#### Subtasks

##### Subtask 1 [20%]

\(N \le 1, x_i, y_i = 0\)

##### Subtask 2 [10%]

\(N \le 3, x_i, y_i = 0\)

##### Subtask 3 [20%]

\(x_i, y_i = 0\)

##### Subtask 4 [50%]

No further constraints.

#### Sample Input 1

```
1
0 0 0 3
```

#### Sample Output 1

`1`

#### Explanation For Sample 1

You are given \(1\) sphere centered at \((0, 0, 0)\) having a radius of \(3\). Of course, this sphere can be in the subset. Thus, the size of the largest subset is \(1\).

#### Sample Input 2

```
4
2 3 3 1
3 -5 10 3
0 0 0 5
4 3 0 1
```

#### Sample Output 2

`3`

#### Explanation For Sample 2

**Note that you do not need to pass this sample to pass some of the subtasks.**

The largest subset consists of selecting the first sphere, the second sphere, and the fourth sphere.

This can be seen from the image below:

The red sphere is the first sphere, the orange sphere is the second sphere, the blue sphere is the third sphere, and the green sphere is the fourth sphere.

## Comments