Problem B
Bubbly Troubly

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 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 overflow 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

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

You may assume that any $2$ glasses that have the same $z$ coordinates will not intersect (though they may touch each other).

Output

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. Always print answers to two decimal places and include the leading $0$ on answers between $0$ and $1$. Output values will always be $\leq 10^6$ seconds (or $11$ days, $13$ hours, $46$ minutes and $40$ seconds, whichever you prefer).

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

84.00

2
2 1 2 2 10
0 0 1 1 10

0.78

2
0 0 1 1 100
10 10 2 1 100

Invalid