Grassland Fence#1526
Near Pemberley Villa, located in the southern district of Byteland, there is a large pasture. Mrs. Darcy is concerned about her delicate plants, which could be trampled by strangers. Therefore, she decided to enclose certain areas of the pasture with triangular fences.
In Mrs. Darcy's basement, there are several fences. She forms each triangular area using exactly three fences, so that each side of the triangle corresponds to one fence. The fences are sturdy and beautiful, so she will not combine multiple fences to form a single side, nor will she cut a fence into shorter pieces. Mrs. Darcy's goal is to enclose the largest possible total area of the pasture.
Each line contains a separate test case. The first number in the line is the number of fences n~(n \le 16) that Mrs. Darcy has. The next integers, each between and , are the lengths of these fences.
For each test case, print in a separate line the maximum area that can be enclosed using the available fences. The answer must be printed with decimal digits.
In the first test case, it is optimal to construct triangles with sides (4, 5, 6) and (7, 8, 9). The total enclosed area in this case is .
In the second test case, the answer is , since it is impossible to form any triangle.
In the third test case, a triangle with sides (4, 4, 4) should be built. Note that fence lengths can repeat.
Example 1