Tetrahedra

Peter P. Pepper는 곤란한 상황에 처했다.

Croode 공국과의 치열한 전투 끝에 그가 섬기는 Aaronbarc 왕국이 최후의 승리를 거두었다. Peter는 전쟁에서 큰 공을 세웠고, 왕은 그에게 큰 상을 주기로 했다. 그러나 심술궂은 왕은 그의 지혜를 시험할 어려운 문제를 냈다. Peter는 여러 개의 막대를 받았고, 이 막대들로 사면체 모양의 그릇을 만들어야 한다. 그러면 그릇의 부피만큼 patas(이 왕국의 화폐)를 받게 될 것이라고 왕이 말했다. 그가 해야 할 일은 그릇의 뼈대를 만드는 것뿐이다.

그림 1: 사면체 그릇의 예

왕은 그릇을 만들 때 두 가지 규칙을 제시했다. (1) 주어진 막대를 모두 사용할 필요는 없다. (2) 더 긴 막대를 만들기 위해 두 개 이상의 막대를 붙여서는 안 된다.

말할 것도 없이 그는 최대한 많은 patas를 받고 싶어 한다. 따라서 그가 받을 수 있는 최대 patas를 알고 싶어 한다. 그래서 그는 친구인 당신을 불러 문제를 해결하는 프로그램을 작성해 달라고 부탁했다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 다음 형식의 한 줄로 주어진다.

N a1 a2 . . . aN

여기서 N은 Peter가 받은 막대의 개수이고, ai는 각 막대의 길이(센티미터)이다. 6 ≤ N ≤ 15이고 1 ≤ ai ≤ 100이라고 가정할 수 있다.

입력은 0 하나만 포함한 줄로 끝난다.

각 테스트 케이스마다 주어진 막대로 만들 수 있는 사면체 그릇의 최대 부피(세제곱센티미터)를 출력한다. 소수점 아래 자릿수는 임의로 출력해도 되지만, 출력값의 오차가 10-6을 넘지 않아야 한다.

각 테스트 케이스마다 적어도 하나의 사면체 그릇을 만들 수 있음이 보장된다.