고스트 버스터즈

시간 제한1초메모리 제한128 MB

요약

원점에서 옥탄트 X,Y,Z >= 0 안으로 쏜 광선이 최대한 많은 구를 스치도록 조준할 때 파괴할 수 있는 구의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 수학, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

고스트 버스터즈 팀이 유령 퇴치 차량 Ecto-1에 강력한 양성자 총과 자동 조준 장치를 새로 장착했습니다. 여러분은 이 조준 소프트웨어의 시제품을 작성하는 일을 맡았습니다.

유령은 스캐너에 공중에 떠 있는 구(sphere)로 감지되며, 각 유령은 중심 좌표와 반지름으로 주어집니다. 양성자 총은 원점 $(0, 0, 0)$ 에서 팔분공간 $X \ge 0,\ Y \ge 0,\ Z \ge 0$ 방향으로만 발사할 수 있습니다. 총은 원점에서 직선으로 뻗어 나가는 하나의 광선을 쏘며, 이 광선이 스치기만 해도 그 유령은 즉시 소멸합니다. 하나의 광선은 그 경로 위에 놓인 유령을 개수 제한 없이 모두 소멸시킬 수 있습니다.

원점에서 쏘는 단 한 번의 발사로 소멸시킬 수 있는 유령의 최대 개수를 구하세요.

입력

첫 번째 줄에 감지된 유령의 수 $N$ ( $0 \le N \le 100$ )이 주어집니다.

이어지는 $N$ 개의 줄에는 각 유령의 정보가 한 줄에 하나씩 주어집니다. 각 줄에는 네 정수 $X_i$ , $Y_i$ , $Z_i$ , $R_i$ 가 공백으로 구분되어 주어지며, $(X_i, Y_i, Z_i)$ 는 유령의 중심 좌표, $R_i$ 는 반지름입니다. $1 \le X_i, Y_i, Z_i \le 10000$ 이고 $1 \le R_i \le \min(X_i, Y_i, Z_i)$ 입니다.

유령은 서로 겹치거나, 하나가 다른 하나의 내부에 들어가거나, 완전히 일치할 수도 있습니다.

출력

단 한 번의 발사로 소멸시킬 수 있는 유령의 최대 개수를 정수 하나로 출력하세요.

예제2

예제 1
입력
```
2
1200 1200 3900 300
160 160 820 60
```
예상 출력
```
2
```

예제 2

입력

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

예상 출력