시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 5 4 3 75.000%

문제

N(3≤N≤40)개의 막대기들이 있다. 각각의 막대기들은 길이가 서로 같은 수도 있고, 서로 다를 수도 있다. 이러한 막대기들을 연결하여 하나의 삼각형을 만들려고 한다. 이 때 사용하지 않는 막대기가 있어서는 안 된다. 즉, 각 막대기들을 적당히 세 그룹으로 나눈 다음, 각 그룹에 있는 막대기들을 일렬로 연결하고, 이를 이용하여 삼각형을 만드는 것이다.

이와 같이 삼각형을 만들었을 때, 가장 큰 삼각형의 넓이를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 막대기의 길이 L(1≤L≤40)이 주어진다.

출력

첫째 줄에 최대 면적을 100배한 값을 소수점 아래에서 버림한 정수를 출력한다. 만약 삼각형을 만들 수 없다면 -1을 출력한다.

예제 입력

5
1
1
3
3
4

예제 출력

692

힌트

삼각형의 세 변의 길이가 a, b, c일 때, s=(a+b+c)/2 로 두면, 넓이의 제곱은 s×(s-a)×(s-b)×(s-c)이 된다.