Globulous Gumdrops#306
Gwen just bought a bag of gumdrops! However, she does not like carrying gumdrops in plastic bags; instead, she wants to pack her gumdrops in a cylindrical tube of diameter . Each gumdrop is a perfect sphere with radii r_1, r_2, \ldots, r_n. Find the shortest length of tube Gwen can use to store her gumdrops.
Assume that the gumdrop radii are sufficiently large so that no three gumdrops can be in contact with each other simultaneously inside the tube. Given this constraint, the gumdrops will always be arranged so that their centers lie on a single two-dimensional plane containing the axis of the tube.
The input contains multiple test cases. Each test case consists of two lines. The first line contains an integer (1 \leq n \leq 15) — the number of gumdrops, and a floating-point number (2.0 \leq d \leq 1000.0) — the diameter of the cylindrical tube. These are separated by a space.
The second line contains space-separated floating-point numbers r_1, r_2, \ldots, r_n (1.0 \leq r_i \leq d / 2) — the radii of the gumdrops.
A blank line separates test cases. A single line with the numbers "0 0" marks the end of input; do not process this case.
For each test case, print the shortest length of tube, rounded to the nearest integer.
Example 1