격자 위의 다각형

일본 어딘가의 신성한 숲 깊은 곳에 있는 가장 이름난 사원에 궁극의 탄트라(Tantra)가 보관되어 있었다고 전해진다. 여러 해에 걸친 열성적인 연구 끝에 고문서학자들은 마침내 그 위치를 밝혀냈는데, 놀랍게도 히요시(Hiyoshi)에 있는 작은 사원이었다. 이 사원에는 거대한 돌로 지어진 지하 밀실이 있으며, 이 거석 구조물이 탄트라가 모셔진 곳으로 여겨진다.

그러나 밀실의 문은 단단히 잠겨 있다. 전설에 따르면 문 자물쇠의 열쇠는 최고위 사제들만이 알던 어떤 정수였다고 한다. 사원을 지은 종파가 쇠퇴하면서 이제 그 정수를 알 수 없게 되었고, 문화청은 문을 부수는 것을 금지하고 있다. 다행히도 그 비밀 숫자를 추측할 단서가 될 수 있는, 여러 개의 막대 그림이 문에 새겨져 있다.

수많은 저명한 학자들이 이 수수께끼에 도전했지만 아무도 풀지 못했는데, 최근 한 뛰어난 젊은 컴퓨터 과학자가 마침내 이 퍼즐을 해독했다. 막대들의 길이는 어떤 단위 길이의 정수배이다. 비밀 숫자를 찾으려면 모든 막대를 그 단위 길이의 격자 위에 놓아 하나의 볼록 다각형을 만들어야 하며, 각 막대의 양 끝은 반드시 격자점 위에 있어야 한다. 초등 수학에 따르면 이 다각형의 넓이는 항상 단위 길이의 제곱의 정수배가 된다. 넓이가 가장 큰 다각형의 넓이가 바로 문을 여는 비밀 숫자이다.

예를 들어 길이가 1, 2, 5, 5, 5인 막대 다섯 개가 있으면 본질적으로 서로 다른 볼록 다각형은 세 가지뿐이며, 그중 최대 넓이는 19이다.

주어진 모든 막대를 사용하고 각 막대의 양 끝이 격자점 위에 있는 볼록 다각형의 최대 넓이를 구하는 프로그램을 작성하시오.

입력은 여러 개의 데이터셋으로 이루어지며, 입력의 끝을 나타내는 0 하나만 있는 줄로 끝난다. 각 데이터셋의 형식은 다음과 같다.

n
r1 r2 ... rn

여기서 n은 막대의 개수를 나타내는 정수로 $3 \le n \le 6$을 만족한다. 각 ri는 i번째 막대의 길이를 나타내는 정수로 $1 \le r_i \le 300$을 만족한다.

각 데이터셋에 대해, 가장 넓은 볼록 다각형의 넓이인 정수를 한 줄에 출력한다. 해당 데이터셋에 대해 가능한 볼록 다각형이 없으면 -1을 출력한다.