조립 장난감

Alaa는 어릴 때 가지고 놀던 조립 장난감을 기억한다. 양 끝을 서로 이어 붙일 수 있는 곧은 막대 여러 개로 된 장난감이었다. Alaa가 좋아한 놀이는 막대 하나를 곧은 벽에 딱 붙여 밑변으로 놓고 시작한다. 그다음에는 삼각형을 하나씩 덧붙인다. 새 삼각형의 한 변은 이미 구조물에 있는 막대이고, 나머지 두 변은 아직 쓰지 않은 막대 두 개다. Alaa는 제대로 된 삼각형만 만들었으므로 두 변의 길이 합이 나머지 한 변의 길이와 같아지는 경우는 없다. 어떤 막대도 벽을 뚫고 지나갈 수 없지만, 새로 붙인 막대가 이미 놓인 막대와 교차하는 것은 허용한다.

Alaa의 목표는 벽에서 최대한 멀리 뻗어 나가는 구조물을 만드는 것이다. 길이가 모두 같은 막대로 쌓으면 시시하니 길이가 서로 다른 막대만 골라 썼다. 일부만 쓰기도 하고 전부 쓰기도 하면서 여러 조합을 시도했다.

아래 그림은 길이가 42, 40, 32, 30, 25, 18, 15인 막대로 만들 수 있는 구조물 몇 가지다. 그중 하나는 벽에서 약 66.9495만큼 떨어진 곳까지 닿는다.

그림: 위 길이로 만든 구조물 후보이고, 각 그림에서 벽은 왼쪽에 있다.

막대 길이가 주어질 때 Alaa의 구조물이 벽에서 도달할 수 있는 가장 먼 거리를 구하라.

입력은 양의 정수로 이루어진 한 줄이다. 첫 정수 $n$은 막대의 개수이고 $3 \le n \le 9$이다. 이어지는 $n$개의 정수 $l_1, l_2, \ldots, l_n$은 막대의 길이이며 $l_1 > l_2 > \cdots > l_n$이고 모든 $j$에 대해 $1 \le l_j \le 99$이다. 주어진 길이로 삼각형을 적어도 하나는 만들 수 있다.

구조물이 벽에서 도달할 수 있는 가장 먼 거리를 소수점 아래 여섯째 자리까지 출력한다.

막대는 각각 최대 한 번만 쓰고, 구조물이 모든 막대를 다 쓸 필요는 없다. 최대 거리에 도달하는 구조물에서 밑변의 두 끝점을 제외한 모든 꼭짓점은 벽에서 $0.0001$ 이상 떨어져 있고, 답이 소수점 아래 여섯째 자리에서 모호해지지 않도록 입력이 주어진다.