Falling Ice

Disks of ice fall one at a time into a box. Each disk drops straight down and comes to rest at the lowest position it can reach without overlapping any disk already in the box and without moving any of them. Once a disk stops it freezes in place and can never be pushed by a later disk. Your task is to compute the total height of the final pile of disks.

To make the answer unique, assume that any disk which reaches the bottom of the box rolls as far to the left as it can. The input is also chosen so that every disk which does not reach the bottom has a single, unambiguous lowest resting position, and so that there are no exact fits: each disk that settles touches exactly two supports (previously placed disks, or the walls and floor of the box).

Note that a disk cannot always reach the lowest empty spot in the box. Because a disk falls from the top, it may become wedged between an earlier disk and a wall (or between two earlier disks) even when there is still room lower down. It simply cannot get there by falling.

You can find the upper intersection point of two overlapping circles as follows. Let circle 1 have center $(x_1, y_1)$ and radius $r_1$, and let circle 2 have center $(x_2, y_2)$ and radius $r_2$, with circle 1 to the left of circle 2 (that is, $x_1 < x_2$). Define

• $dx = x_2 - x_1$,
• $dy = y_2 - y_1$,
• $D = \sqrt{dx^2 + dy^2}$,
• $E = \dfrac{r_1^2 - r_2^2 + D^2}{2D}$,
• $F = \sqrt{r_1^2 - E^2}$.

Then the upper intersection point is

$\left(x_1 + \frac{E\,dx - F\,dy}{D},\; y_1 + \frac{F\,dx + E\,dy}{D}\right).$

The input consists of one or more data sets, followed by a line containing only $0$ that marks the end of the input. Each data set is given on its own line as a sequence of three or more blank-separated positive integers in the form $w\ n\ d_1\ d_2\ \dots\ d_n$, where $w$ is the width of the box, $n$ is the number of disks, and $d_1, d_2, \dots, d_n$ are the diameters of the disks in the order in which they fall into the box. You may assume that $w < 100$, that $n < 10$, and that every diameter is smaller than $w$.

For each data set, print a single line containing the height of the pile of disks, rounded to two digits after the decimal point.