샴페인 타워

결혼식이나 파티에서 샴페인 타워를 본 적이 있을 것이다. 흔한 3층 타워라면 맨 아래 1층에 잔 9개가 정사각형 모양으로 맞닿아 있고, 2층에는 잔 4개가 1층 한가운데 위에 정사각형 모양으로 맞닿아 있으며, 3층에는 잔 1개가 두 층의 한가운데 위에 놓인다. 그림 1은 이 타워를 위에서 내려다본 모습이다.

그림 1

샴페인은 언제나 맨 위 잔에만 붓는다. 이 예에서 맨 위 잔이 가득 차서 넘치기 시작하면 곧바로 아래 잔 4개가 차기 시작한다. 넘친 샴페인이 아래 잔까지 내려가는 데 걸리는 시간은 0으로 본다. 2층의 잔 4개가 가득 차면 1층의 잔 9개로 넘친다. 이 예에서 2층의 네 잔은 동시에 가득 차지만 1층의 아홉 잔은 서로 다른 시각에 가득 찬다. 그래서 타워가 다 차기 전에 바닥으로 흘러 버리는 샴페인이 생긴다. 이 정도 손실은 아름다운 광경을 위해 감수할 만하다.

요즘은 잔을 늘어놓아 무늬나 그림을 만드는 방식이 유행이다. 이런 타워는 구조적으로 안정적이지 않아도 된다. 넘치는 샴페인을 방해하지 않도록 설계한 받침 장치가 잔을 제자리에 붙잡아 준다. 어떤 타워든 샴페인을 직접 붓는 가장 높은 잔이 정확히 하나 있다.

잔의 테두리는 위에서 보면 원이다. 넘침은 다음 규칙을 따른다.

• 잔이 가득 찬 뒤에 들어오는 샴페인은 테두리 원 전체를 따라 고르게 넘쳐 수직으로 곧장 아래로 떨어진다.
• 떨어지는 지점이 어떤 잔의 테두리 원 내부에 들어가면 그 잔이 받는다. 넘치는 잔보다 $z$가 작은 잔만 받을 수 있다. 그 지점을 내부에 담는 잔이 여럿이면 $z$가 가장 큰 잔이 받는다.
• 두 잔의 테두리가 수직으로 정확히 겹치면, 즉 중심과 반지름이 모두 같으면 위 잔에서 아래 잔으로 쌓이는 샴페인은 없다. 위 잔에서 넘친 샴페인이 다른 더 낮은 잔에 모이는 것은 여전히 가능하다.
• 넘침이 한 점에서만 일어나면 쌓이는 양은 0이다. 길이가 0보다 큰 호가 잔 내부로 넘칠 때만 샴페인이 실제로 쌓인다.

주어진 샴페인 타워가 완전히 가득 차는지 판정하고, 찬다면 걸리는 시간을 구하는 프로그램을 작성하시오.

첫째 줄에 타워를 이루는 잔의 개수 $n$이 주어진다 ($1 \le n \le 20$). 다음 $n$개의 줄에는 잔 하나를 설명하는 정수 다섯 개 $x$ $y$ $z$ $r$ $v$가 주어진다. $(x, y, z)$는 잔 테두리의 중심이고 ($0 \le x, y \le 1000$, $1 \le z \le 1000$), $r$은 테두리의 반지름이며 ($1 \le r \le 1000$), $v$는 잔의 용량으로 단위는 밀리리터다 ($1 \le v \le 1000$). 모든 입력값은 정수다. $z$가 가장 큰 잔은 언제나 하나뿐이고, 그 잔에 1초당 100밀리리터씩 일정하게 샴페인을 붓는다.

타워가 완전히 가득 차는 시각을 초 단위로 출력한다. 끝내 가득 차지 않으면 Invalid를 출력한다. 답은 소수점 아래 셋째 자리에서 반올림해 둘째 자리까지 출력하고, 0과 1 사이의 값에는 앞의 0을 붙인다. 출력값은 언제나 $10^6$초 이하다.