떨어지는 얼음 원반

얼음 원반들이 한 번에 하나씩 상자 안으로 떨어집니다. 각 원반은 수직으로 낙하하여, 이미 상자 안에 있는 다른 원반들과 겹치지 않고 또 그것들을 밀지도 않으면서 도달할 수 있는 가장 낮은 위치에 멈춥니다. 원반은 한번 멈추면 그 자리에 얼어붙어, 이후에 떨어지는 원반이 밀 수 없습니다. 최종적으로 쌓인 원반 더미 전체의 높이를 구하세요.

답이 유일하게 정해지도록, 상자의 바닥에 도달한 원반은 가능한 한 왼쪽까지 굴러간다고 가정합니다. 또한 입력 데이터는 바닥에 도달하지 못한 원반이라도 가장 낮은 정지 위치가 유일하게 정해지도록, 그리고 '딱 맞게 끼는' 경우가 없도록 주어집니다. 즉, 멈춘 각 원반은 정확히 두 개의 대상(먼저 놓인 원반들, 또는 상자의 벽과 바닥)과만 접촉합니다.

원반이 언제나 상자에서 가장 낮은 빈 공간에 도달할 수 있는 것은 아님에 유의하세요. 원반은 위에서 떨어지기 때문에, 더 아래에 공간이 남아 있더라도 먼저 놓인 원반과 벽 사이(또는 두 원반 사이)에 끼어 멈출 수 있습니다. 단지 떨어지는 방식만으로는 그 아래 공간까지 갈 수 없기 때문입니다.

서로 겹치는 두 원의 위쪽 교점은 다음과 같이 구할 수 있습니다. 원 1의 중심이 $(x_1, y_1)$이고 반지름이 $r_1$, 원 2의 중심이 $(x_2, y_2)$이고 반지름이 $r_2$이며, 원 1이 원 2의 왼쪽에 있다고($x_1 < x_2$) 하겠습니다. 이때

• $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}$

로 두면, 위쪽 교점은

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

입니다.

입력은 하나 이상의 데이터 집합으로 이루어지며, 마지막에는 $0$ 하나만 있는 줄이 와서 입력의 끝을 나타냅니다. 각 데이터 집합은 한 줄에 주어지며, 공백으로 구분된 세 개 이상의 양의 정수 $w\ n\ d_1\ d_2\ \dots\ d_n$ 형태입니다. 여기서 $w$는 상자의 너비, $n$은 원반의 개수, $d_1, d_2, \dots, d_n$은 상자에 떨어지는 순서대로 나열한 각 원반의 지름입니다. $w < 100$, $n < 10$이며, 모든 지름은 $w$보다 작다고 가정해도 됩니다.

각 데이터 집합에 대해, 쌓인 원반 더미의 높이를 소수점 아래 둘째 자리까지 반올림하여 한 줄에 출력하세요.