Fences

Time limit2sMemory limit128 MB

Summary

Partition up to 16 given fence lengths into disjoint triples, keep only triples that form a valid triangle, and maximize the total area.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Brute force, Geometry
Solved: No attempts yet

Problem

You have N fences with fixed lengths on a wide field. By choosing three distinct fences, you can make one triangular fence; each side of the triangle is one fence. Fences cannot be joined or cut, and a fence used in one triangle cannot be used again in another triangle.

Choose the triangles to build so that the sum of their areas is as large as possible. Compute the maximum possible total area.

Input

The first line contains the number of fences N. N is a positive integer not greater than 16.

The second line contains the length of each fence. Each length is a positive integer not greater than 100.

Output

Print the maximum possible sum of triangle areas on the first line. An absolute or relative error up to 10^-9 is allowed.

Hint

For three lengths $A$ , $B$ , and $C$ with $A \le B \le C$ , a triangle can be made only when $A+B>C$ . Its area is $\sqrt{p(p-A)(p-B)(p-C)}$ , where $p=(A+B+C)/2$ .

Examples4

Example 1
Input
```
7
3 4 5 6 7 8 9
```
Expected output
```
36.754383146489694
```
Example 2
Input
```
4
1 2 4 8
```
Expected output
```
0.0
```
Example 3
Input
```
4
7 4 4 4
```
Expected output
```
6.928203230275509
```

Example 4

Input

16
21 72 15 55 16 44 54 63 69 35 75 69 76 70 50 81

Expected output

7512.322360676162