ICPC East Central NA Regional Contest 2016, Problem A

You may have seen a champagne tower at a wedding or an exclusive Hollywood A-list party. In a typical three-level tower, the first (lowest) level contains $9$ glasses touching in a square pattern. The second level contains $4$ glasses touching in a square pattern centered above the first level, and the third level contains $1$ glass centered above the other levels. Figure 1 shows a top-down view of this tower.

Figure 1: Top-down view of a three-level champagne tower.

Champagne is always poured directly into the top glass. In this example, once the top glass fills and starts to overflow, it immediately begins filling the $4$ glasses below (i.e., assume overflowing champagne travels instantaneously to any glasses below). Once the $4$ glasses on the second level fill, they begin overflowing to the $9$ on the bottom level. Note that in this example the $4$ on the second level finish filling at the same time, but the $9$ on the lowest level finish filling at different times. This means that there will be some amount of spilled champagne before the tower has finished filling – this is an acceptable price to pay for such a beautiful sight.

The new fad is to make interesting patterns or imagery out of champagne glasses. These new-fangled "towers" needn't appear structurally sound; they can be held in place with complex support systems designed so as not to interfere with the overflowing champagne. Each of these new towers will always have a single highest glass into which all champagne is directly poured.

If two glass rims coincide vertically (i.e., have the same center and radius), then no accumulation occurs into the lower glass from the upper glass (though the overflowing champagne from the upper glass may still be collected by other lower glasses). Additionally, a single point of champagne overflow causes no measurable accumulation. In other words, measurable accumulation only occurs when a non-point arc of champagne overflows to the interior of a glass.

Your task is to determine whether a proposed champagne tower will fill to completion, and if so, how long it will take.

Input Specification

The input begins with a single integer $n$ representing the number of champagne glasses in the tower $(1\le n\le 20)$. The next $n$ lines each describe a champagne glass. Each glass description consists of 5 values $xyzrv$ with $(x,y,z)$ representing the center of the glass's rim $(0\le x,y\le 1000;1\le z\le 1000)$, $r$ representing its radius $(1\le r\le 1000)$, and $v$ representing its volume measured in milliliters $(1\le v\le 1000)$. All input values are integers, and the top glass is filled at a constant $100$ milliliters per second.

Output Specification

Display the number of seconds after which the tower will be completely filled, or Invalid if the proposed champagne tower will never fill completely. Round answers to the hundredths place. Output values will always be $\le {10}^6$ seconds (or $11$ days, $13$ hours, $46$ minutes and $40$ seconds, whichever you prefer).

Sample Input 1

14
0 0 1 1 400
0 2 1 1 400
0 4 1 1 400
2 0 1 1 400
2 2 1 1 400
2 4 1 1 400
4 0 1 1 400
4 2 1 1 400
4 4 1 1 400
1 1 2 1 400
1 3 2 1 400
3 1 2 1 400
3 3 2 1 400
2 2 3 1 400

Sample Output 1

84.00

Sample Input 2

2
2 1 2 2 10
0 0 1 1 10

Sample Output 2

0.78

Sample Input 3

2
0 0 1 1 100
10 10 2 1 100

Sample Output 3

Invalid